企业官网建设流程全解析

以ListDictionary为例，在源码中，看不到Array类型的的变量，取而代之的是一个DictionaryNode类型的变量，查看该类的源码会发现，只包含一个key，一个value，和一个DictionaryNode类型的next变量，DictionaryNode的代码如下：

<span style="color:#000000"><span style="background-color:#ffffff"><span style="color:#0000ff">private class </span><span style="color:#2b91af">DictionaryNode </span>{ <span style="color:#0000ff">public object </span>key; <span style="color:#0000ff">public </span><span style="color:#2b91af">ListDictionary</span>.DictionaryNode next; <span style="color:#0000ff">public object </span>value; }</span></span>

添加数据的时候，直接把当前节点的next变量赋值为新的节点，这样一个节点扣一个节点，就有了链的形式。

在链表中查找数据时，如调用Contains(object key) ：bool 方法，需要从链表的头节点依次遍历，逐个匹配，所以时间复杂度为O(n)，和List<T>，ArrayList相比，在查询效率上并没有太大的区别。

那么链表的优势在哪里呢？答案是，节省内存空间。

在之前的文章有提到过，线性表和哈希表初始化时会将内部Array数组默认一个大小，List<T>的初始值为4，Hashtable的为11，当添加数据碰到容量不足时，会将当前数组扩充2倍，这种做法不可避免要造成浪费。而链表不用数组保存，用节点相连，实实在在，添加几个节点，就占用几个节点的内存，相对于线性表和哈希表，链表没有浪费，因而占用内存空间较少。

除了节省空间以外，链表还有一个优点，那就是插入数据的灵活性。

可惜这一点在ListDictionary中并没有体现，每次添加数据，ListDictionary都要遍历整个链表，来确保没有重复节点，导致每次添加都要循环一次，添加数据的时间复杂度和查询数据的时间复杂度都为O（n），比线性表和哈希表要慢的多。

HybridDictionary-结合链表和哈希表的特点扬长避短

在.net的集合容器中，有一个名为HybridDictionary的类，充分利用了Hashtable查询效率高和ListDictionary占用内存空间少的优点，内置了Hashtable和ListDictionary两个容器，添加数据时内部逻辑如下：

当数据量小于8时，Hashtable为null，用ListDictionary保存数据。

当数据量大于8时，实例化Hashtable，数据转移到Hashtable中，然后将ListDictionary置为null。

HybridDictionary的Add方法的代码如下：

<span style="color:#000000"><span style="background-color:#ffffff"><span style="color:#0000ff">public void </span>Add(<span style="color:#0000ff">object </span>key, <span style="color:#0000ff">object </span>value) { <span style="color:#0000ff">if </span>(<span style="color:#0000ff">this</span>.hashtable != <span style="color:#0000ff">null</span>) { <span style="color:#0000ff">this</span>.hashtable.Add(key, value); } <span style="color:#0000ff">else if </span>(<span style="color:#0000ff">this</span>.list == <span style="color:#0000ff">null</span>) { <span style="color:#0000ff">this</span>.list = <span style="color:#0000ff">new </span><span style="color:#2b91af">ListDictionary</span>(<span style="color:#0000ff">this</span>.caseInsensitive ? <span style="color:#2b91af">StringComparer</span>.OrdinalIgnoreCase : <span style="color:#0000ff">null</span>); <span style="color:#0000ff">this</span>.list.Add(key, value); } <span style="color:#0000ff">else if </span>((<span style="color:#0000ff">this</span>.list.Count + 1) >= 9) { <span style="color:#008000">//当数据量大于8时，则调用该方法，实例化Hashtable，转移数据，清空list </span><span style="color:#0000ff">this</span>.ChangeOver(); <span style="color:#0000ff">this</span>.hashtable.Add(key, value); } <span style="color:#0000ff">else </span>{ <span style="color:#0000ff">this</span>.list.Add(key, value); } }</span></span>

HybridDictionary类也进一步说明出了链表ListDictionary的特点：相对于Hashtable，占用内存较少，但随着数据量的增加，查询效率远不及Hashtable。

泛型链表-LinkedList<T>

LinkedList是泛型链表，也是用节点存取，节点类型为LinkedListNode<T> ，与ListDictionary的节点不同的是，LinkedListNode<T>有next和prev两个指向，说明LinkedList<T>是双向链表，而ListDictionary是单向链表，代码如下：

<span style="color:#000000"><span style="background-color:#ffffff"><span style="color:#0000ff">public sealed class </span><span style="color:#2b91af">LinkedListNode</span><T> { <span style="color:#008000">// Fields </span><span style="color:#0000ff">internal </span>T item; <span style="color:#0000ff">internal </span><span style="color:#2b91af">LinkedList</span><T> list; <span style="color:#0000ff">internal </span><span style="color:#2b91af">LinkedListNode</span><T> next; <span style="color:#0000ff">internal </span><span style="color:#2b91af">LinkedListNode</span><T> prev; ...... }</span></span>

除了节省内存空间外，链表的另一个优点--插入数据的灵活性，在LinkedList<T>中完全体现出来，共有4个不同位置的添加数据的方法，分别为链头插入，链尾插入，节点前插入，节点后插入。

每种插入方法又分别有两种插入模式：

1、直接插入LinkedListNode<T>，没有返回值。

2、直接插入T类型的值，返回插入完成后的节点。

四种位置，两种模式，一共就有8个插入数据的方法，运用这些方法，可以在添加数据时灵活控制链表中数据的顺序，这个优势是线性表和哈希表所不能比的。代码如下：

<span style="color:#000000"><span style="background-color:#ffffff"><span style="color:#0000ff">public </span><span style="color:#2b91af">LinkedListNode</span><T> AddAfter(<span style="color:#2b91af">LinkedListNode</span><T> node, T value); <span style="color:#0000ff">public void </span>AddAfter(<span style="color:#2b91af">LinkedListNode</span><T> node, <span style="color:#2b91af">LinkedListNode</span><T> newNode); <span style="color:#0000ff">public void </span>AddBefore(<span style="color:#2b91af">LinkedListNode</span><T> node, <span style="color:#2b91af">LinkedListNode</span><T> newNode); <span style="color:#0000ff">public </span><span style="color:#2b91af">LinkedListNode</span><T> AddBefore(<span style="color:#2b91af">LinkedListNode</span><T> node, T value); <span style="color:#0000ff">public void </span>AddFirst(<span style="color:#2b91af">LinkedListNode</span><T> node); <span style="color:#0000ff">public </span><span style="color:#2b91af">LinkedListNode</span><T> AddFirst(T value); <span style="color:#0000ff">public </span><span style="color:#2b91af">LinkedListNode</span><T> AddLast(T value); <span style="color:#0000ff">public void </span>AddLast(<span style="color:#2b91af">LinkedListNode</span><T> node);</span></span>

此外，由于LinkedList<T>是双向链表，在查询数据方面提供了“从前往后”和“从后往前”两个查询方法，所以虽然理论上链表的时间复杂度为O（n），根据自己在插入数据时对顺序的把握，结合这两个方法，可以相对提高查询效率。

<span style="color:#000000"><span style="background-color:#ffffff"><span style="color:#0000ff">public </span><span style="color:#2b91af">LinkedListNode</span><T> Find(T value);<span style="color:#9bbb59"><span style="color:#008040">//从前往后查</span> </span><span style="color:#0000ff">public </span><span style="color:#2b91af">LinkedListNode</span><T> FindLast(T value);<span style="color:#008080">//从后往前查 </span></span></span>

结论