一个最基本的HashedLinkedList
2013-01-07 23:52 by 老赵, 2983 visitsTmc的初衷是补充一些常用的数据结构，例如对null作为字典键的支持，以及带有一个额外Remove方法的HashDictionary。但是，其实我创建Tmc项目的“初衷”却是HashedLinkedList。.NET BCL中已经有一个LinkedList，这是一个双向链表。说起来，我之前在面试中经常会提出一系列数据结构的基础问题，其中便包含LinkedList，我会问各个操作的时间复杂度，以及如何改进它们。例如，如何将它的Remove操作优化成O(1)的时间复杂度？最容易想到的做法便是使用一个字典来记录元素到特定LinkedListNode的映射关系。这种模式实在过于常见，所以便有了个特别的名称，叫做HashedLinkedList。
好吧，其实在C5中已经有了一个HashedLinkedList类，但是有重大缺陷，例如没有暴露出LinkedListNode这个类型。我们来看下.NET BCL中LinkedList的一些方法：
public class LinkedListNode<T> { public LinkedList<T> List { get; } public LinkedListNode<T> Next { get; } public LinkedListNode<T> Previous { get; } public T Value { get; set; } } public class LinkedList<T> { public LinkedListNode<T> AddFirst(T value); public LinkedListNode<T> AddLast(T value); public LinkedListNode<T> AddBefore(LinkedListNode<T> node, T value); public LinkedListNode<T> AddAfter(LinkedListNode<T> node, T value); // ... }
.NET BCL的LinkedList会暴露出配套的LinkedListNode，这样我们便可以保留LinkedListNode对象，并执行O(1)实现复杂度的快速插入。此外，我们还可以根据LinkedListNode的Next和Previous进行前后遍历，这才是真正的“链表”。之前有人问我，为什么LinkedList不实现IList接口呢？我的看法就是LinkedList和List在表现上的区别实在太大，而IList的含义是后者，因此就放过LinkedList了。
其实，完全从外部实现一个HashedLinkedList（的部分功能）也不难，我们只要封装一个LinkedList和一个Dictionary即可。例如：
public class HashedLinkedList<T> { private readonly LinkedList<T> _list = new LinkedList<T>(); private readonly Dictionary<T, LinkedListNode<T>> _nodes = new Dictionary<T, LinkedListNode<T>>(); public LinkedListNode<T> AddLast(T value) { var node = _list.AddLast(value); _nodes.Add(value, node); return node; } public void Remove(T value) { var node = _nodes[value]; _nodes.Remove(value); _list.Remove(node); } }
当然，这种“粗制滥造”的HashedLinkedList类完全不能作为通用的数据结构来使用，但假如是普通项目需要，这么做往往也够了。而且事实上一个“通用”的HashLinkedList的确也会遇到很多决策问题，例如：是否支持相同元素？我们知道.NET BCL中的LinkedList是支持相同元素的（事实上LinkedListNode的Value属性可读可写），但显然上面这个粗糙的HashedLinkedList便不支持。
有人可能会说，支持相同元素很容易呀，只要用Dictionary<T, List<LinkedListNode>>或类似的结构，将一个值映射到多个LinkedListNode就行了。这可能会解决一部分问题，但事情远没有那么简单。例如.NET BCL的LinkedList还有Find(T value)和FindLast(T value)这两个方法，分别用来找出“第一个”和“最后一个”与value相等的LinkedListNode。没错，LinkedList是有顺序的，假如我们要保留Find和FindLast的语义不变，就没法提供O(1)的时间复杂度的实现——不信你试试看？
假如我们还是用遍历的方法来实现Find和FindLast，这便失去了HashedLinkedList的意义。但是反过来说，在很多时候，我们可以确定不需要其支持相同元素，或者无所谓Find得到的是其中的哪个节点呐。我估计这也是.NET BCL中不提供HashedLinkedList的缘故吧，既然没法“通用”，那么就由开发人员自己根据需要来组合吧。
目前在Tmc中的HashedLinkedList便不支持保存相同元素，它只是将.NET BCL的LinkedList几乎原封不动地复制过来，然后增加一些简单的功能。.NET BCL的LinkedList的实现为“双向循环链表”，不同于某些数据结构书上使用head和tail来保存首尾节点，“双向循环列表”只需要记录头节点，而尾节点只需要简单的访问“头节点”的“前一个节点”即可：
private LinkedListNode<T> _head; public LinkedListNode<T> Last { get { return _head == null ? null : _head._prev; } }
使用“双向循环列表”的好处在于实现特别简单，各种修改操作都能统一为三个方法：
private void InsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode); private void InsertNodeToEmptyList(LinkedListNode<T> newNode); private void RemoveNode(LinkedListNode<T> node);
因此，在此基础上实现的HashedLinkedList也只需要修改这三个方法即可，几乎是瞬间的事情。当然，假如只是这样的HashedLinkedList，我将其放入Tmc项目的意义也不大。因此，不久的将来我会删除这个类，并提供额外的数据结构来应对不同的需求：
- 不支持相同元素。
- 支持相同元素，但不保证顺序，效率比前者略低。
- 支持相同元素，并保证顺序，效率比前两者低，但肯定要高于.NET BCL中自带的
LinkedList。
这种数据结构（亦或是三种？），我就称之为IndexedLinkedList吧。假如是你，你会怎么做呢？
不知老赵还有没有关注F#？问个不相关的问题。
我有个长期运行的程序的并行核心用F#的MailBox实现，但线上运行n天后出现丢消息的情况。通过日志打点，我已确认代码能运行到分发函数里的Agent.Post方法上，但是在agent body里没反应。在本机调试上又重现不出这个bug。我已经快要被这个幽灵bug搞疯了……