【C#食谱】【面食】菜单4：List和LinkedList性能比较

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› Node.js›Node.js教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

首先，先说明一下，LinkedList<T>其实是一个双向链表：

一个LinkedList<T>对象其实就是一系列LinkedListNode<T>对象的集合。每一个LinkedListNode<T>对象都可以访问下一个和前一个LinkedListNode<T>对象，其值是通过value属性访问的。

现在，开始我们的性能比较：List<T>类的性能优于LinkedList<T>类。

增加删除
在List<T>中增加、删除节点的速度，大体上快于使用LinkedList<T>时的相同操作。将 List<T>.Add方法和LinkedList<T>的Add*方法相比较，真正的性能差别不在于Add操作，而在LinkedList<T>在给GC（垃圾回收机制）的压力上。一个List<T>本质上是将其数据保存在一个堆栈的数组上，而LinkedList<T>是将其所有节点保存在堆栈上（人家是一个，我是一系列）。这就使得GC需要更多地管理堆栈上LinkedList<T>的节点对象。注意，List<T>.Insert*方法比在LinkedList<T>中使用Add*方法在任何地方添加一个节点可能要慢。然而，这个依赖于List<T>插入对象的位置。Insert方法必须使所有在插入点后面的元素往后移动一位。如果新元素被插在List<T>最后或接近最后的位置，那么相对于GC维护LinkedList<T>节点的总的开销来说，其开销是可以被忽略的。

索引
另一个List<T>性能优于LinkedList<T>的地方是你在使用索引进行访问的时候。在List<T>中，你可以使用索引值（indexer）直接定位到某个具体的元素位置。而在LinkedList<T>中，却没有这样的奢侈品。在LinkedList<T>中，你必须通过Previous或Next属性遍历整个List，直到找到你想要的节点。

搜索查找
在搜索某个元素或节点的时候，List<T>的性能也优于LinkedList<T>。相比于LinkedList<T>的Contains,Find，和FindLast方法，List<T>.BinarySearch方法在找元素方面更快。这次因为LinkedList<T>使用的是线性查找，而List<T>使用的是Binary Search。简单地说，Binary Search利用List<T>中的元素已排过序，这需要在调用BinarySearch方法之前先调用Sort方法（请注意，如果有任何新的元素被添加进来，那么Sort方法必须被重新调用）。接下去的查找就是Binary Search的算法了，我就不再赘述了！