以ListDictionary为例在源码中看不到Array类型的的变量取而代之的是一个DictionaryNode类型的变量查看该类的源码会发现只包含一个key一个value和一个DictionaryNode类型的next变量DictionaryNode的代码如下span stylecolor:#000000span stylebackground-color:#ffffffspan stylecolor:#0000ffprivate class /spanspan stylecolor:#2b91afDictionaryNode /span{ span stylecolor:#0000ffpublic object /spankey; span stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afListDictionary/span.DictionaryNode next; span stylecolor:#0000ffpublic object /spanvalue; }/span/span添加数据的时候直接把当前节点的next变量赋值为新的节点这样一个节点扣一个节点就有了链的形式。在链表中查找数据时如调用Contains(object key) bool 方法需要从链表的头节点依次遍历逐个匹配所以时间复杂度为O(n)和ListTArrayList相比在查询效率上并没有太大的区别。那么链表的优势在哪里呢答案是节省内存空间。在之前的文章有提到过线性表和哈希表初始化时会将内部Array数组默认一个大小ListT的初始值为4Hashtable的为11当添加数据碰到容量不足时会将当前数组扩充2倍这种做法不可避免要造成浪费。而链表不用数组保存用节点相连实实在在添加几个节点就占用几个节点的内存相对于线性表和哈希表链表没有浪费因而占用内存空间较少。除了节省空间以外链表还有一个优点那就是插入数据的灵活性。可惜这一点在ListDictionary中并没有体现每次添加数据ListDictionary都要遍历整个链表来确保没有重复节点导致每次添加都要循环一次添加数据的时间复杂度和查询数据的时间复杂度都为On比线性表和哈希表要慢的多。HybridDictionary-结合链表和哈希表的特点扬长避短在.net的集合容器中有一个名为HybridDictionary的类充分利用了Hashtable查询效率高和ListDictionary占用内存空间少的优点内置了Hashtable和ListDictionary两个容器添加数据时内部逻辑如下当数据量小于8时Hashtable为null用ListDictionary保存数据。当数据量大于8时实例化Hashtable数据转移到Hashtable中然后将ListDictionary置为null。HybridDictionary的Add方法的代码如下span stylecolor:#000000span stylebackground-color:#ffffffspan stylecolor:#0000ffpublic void /spanAdd(span stylecolor:#0000ffobject /spankey, span stylecolor:#0000ffobject /spanvalue) { span stylecolor:#0000ffif /span(span stylecolor:#0000ffthis/span.hashtable ! span stylecolor:#0000ffnull/span) { span stylecolor:#0000ffthis/span.hashtable.Add(key, value); } span stylecolor:#0000ffelse if /span(span stylecolor:#0000ffthis/span.list span stylecolor:#0000ffnull/span) { span stylecolor:#0000ffthis/span.list span stylecolor:#0000ffnew /spanspan stylecolor:#2b91afListDictionary/span(span stylecolor:#0000ffthis/span.caseInsensitive ? span stylecolor:#2b91afStringComparer/span.OrdinalIgnoreCase : span stylecolor:#0000ffnull/span); span stylecolor:#0000ffthis/span.list.Add(key, value); } span stylecolor:#0000ffelse if /span((span stylecolor:#0000ffthis/span.list.Count 1) 9) { span stylecolor:#008000//当数据量大于8时则调用该方法实例化Hashtable转移数据清空list /spanspan stylecolor:#0000ffthis/span.ChangeOver(); span stylecolor:#0000ffthis/span.hashtable.Add(key, value); } span stylecolor:#0000ffelse /span{ span stylecolor:#0000ffthis/span.list.Add(key, value); } }/span/spanHybridDictionary类也进一步说明出了链表ListDictionary的特点相对于Hashtable占用内存较少但随着数据量的增加查询效率远不及Hashtable。泛型链表-LinkedListTLinkedList是泛型链表也是用节点存取节点类型为LinkedListNodeT 与ListDictionary的节点不同的是LinkedListNodeT有next和prev两个指向说明LinkedListT是双向链表而ListDictionary是单向链表代码如下span stylecolor:#000000span stylebackground-color:#ffffffspan stylecolor:#0000ffpublic sealed class /spanspan stylecolor:#2b91afLinkedListNode/spanT { span stylecolor:#008000// Fields /spanspan stylecolor:#0000ffinternal /spanT item; span stylecolor:#0000ffinternal /spanspan stylecolor:#2b91afLinkedList/spanT list; span stylecolor:#0000ffinternal /spanspan stylecolor:#2b91afLinkedListNode/spanT next; span stylecolor:#0000ffinternal /spanspan stylecolor:#2b91afLinkedListNode/spanT prev; ...... }/span/span除了节省内存空间外链表的另一个优点--插入数据的灵活性在LinkedListT中完全体现出来共有4个不同位置的添加数据的方法分别为链头插入链尾插入节点前插入节点后插入。每种插入方法又分别有两种插入模式1、直接插入LinkedListNodeT没有返回值。2、直接插入T类型的值返回插入完成后的节点。四种位置两种模式一共就有8个插入数据的方法运用这些方法可以在添加数据时灵活控制链表中数据的顺序这个优势是线性表和哈希表所不能比的。代码如下span stylecolor:#000000span stylebackground-color:#ffffffspan stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afLinkedListNode/spanT AddAfter(span stylecolor:#2b91afLinkedListNode/spanT node, T value); span stylecolor:#0000ffpublic void /spanAddAfter(span stylecolor:#2b91afLinkedListNode/spanT node, span stylecolor:#2b91afLinkedListNode/spanT newNode); span stylecolor:#0000ffpublic void /spanAddBefore(span stylecolor:#2b91afLinkedListNode/spanT node, span stylecolor:#2b91afLinkedListNode/spanT newNode); span stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afLinkedListNode/spanT AddBefore(span stylecolor:#2b91afLinkedListNode/spanT node, T value); span stylecolor:#0000ffpublic void /spanAddFirst(span stylecolor:#2b91afLinkedListNode/spanT node); span stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afLinkedListNode/spanT AddFirst(T value); span stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afLinkedListNode/spanT AddLast(T value); span stylecolor:#0000ffpublic void /spanAddLast(span stylecolor:#2b91afLinkedListNode/spanT node);/span/span此外由于LinkedListT是双向链表在查询数据方面提供了“从前往后”和“从后往前”两个查询方法所以虽然理论上链表的时间复杂度为On根据自己在插入数据时对顺序的把握结合这两个方法可以相对提高查询效率。span stylecolor:#000000span stylebackground-color:#ffffffspan stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afLinkedListNode/spanT Find(T value);span stylecolor:#9bbb59span stylecolor:#008040//从前往后查/span /spanspan stylecolor:#0000ffpublic /spanspan stylecolor:#2b91afLinkedListNode/spanT FindLast(T value);span stylecolor:#008080//从后往前查 /span/span/span结论