LinkedList和List在三种简单算法中效率比较

LinkedList和List在三种简单算法中效率比较2011-02-26eaglet.Net 框架提供了两种List类型，一种是基于链表的LinkedList, 一种是基于数组的List。那么在实际应用中到底采用哪种List，如何取舍呢？本文对两种类型在队列，堆栈和简单插入三种简单算法中的效率进行了一个比较。

首先先让我们来看一下List的初始容量Capacity对List的性能是否有影响。

测试方法：分别设置初始容量为0，64，255，1024. List插入的最大长度为1000，循环1000次，得到如下结果，单位为ms，下同。

算法/初始容量	0	64	255	1024
队列	35837	35753	37171	35711
堆栈	302	279	298	289
简单插入	100	105	100	100

从上面数据中我们可以看出List的初始容量对效率没有明显影响。

队列算法比较

测试方法：对LinkedList和List采用先进先出的队列算法，分别设置队列最大长度为10，30，50，100，1000，10000，并循环1000次，得到如下结果。

List类型/队列最大长度	10	30	50	100	1000	10000
LinkedList	0.7659	0.8768	1.1041	2.0401	61	691
List	0.3326	1.1677	1.9985	12	443	37516

从测试结果中我们可以看出LinkedList 随着最大队列长度的增加，所用时间基本成线性增长。而List则成指数增长。我分析主要原因应该是每次删除List的数组头时，List都要做一次整个数数组的拷贝，而链表类型则不存在这个问题。有趣的是当队列长度小于30时，List的效率要比LinkedList要高，这主要是因为链表在增删元素时需要额外创建链表指针，而数组不需要这个操作。在队列长度较小时，这种开销就会显得很明显。

堆栈算法比较

测试方法：对LinkedList和List采用先进后出的堆栈算法，分别设置队列最大长度为10，30，50，100，1000，10000，并循环1000次，得到如下结果。

List类型/堆栈最大长度	10	30	50	100	1000	10000
LinkedList	0.8515	0.9295	1.1123	2.1874	58	714
List	0.1109	0.3104	0.5118	1.2256	29	284

从测试结果看两种类型都是线性增长，但List的性能更高一些。我分析这主要是因为List类型在增长到最大值后在从尾部删除元素，其并不重新分配内存，除非你强行让它压缩。所以List从尾部删除只是将Count改变了一下，因此效率很高。而链表类型的效率和队列方式基本相当，这也是在预料之中的，其效率比List低的原因主要还是在增删时创建和删除节点的额外开销。

简单插入算法比较

测试方法：对LinkedList和List采用向后追加若干元素的算法，分别设置插入最大长度为10，30，50，100，1000，10000，并循环1000次，得到如下结果。

List类型/插入最大长度	10	30	50	100	1000	10000
LinkedList	0.6778	0.765	0.938	1.7783	40	535
List	0.0864	0.1661	0.2509	0.4312	10	109

其测试结果和堆栈算法基本类似，且List的效率更高，这里不再重复论述。