.Net 框架提供了两种List类型，一种是基于链表的LinkedList, 一种是基于数组的List。那么在实际应用中到底采用哪种List，如何取舍呢?本文对两种类型在队列，堆栈和简单插入三种简单算法中的效率进行了一个比较。
首先先让我们来看一下List的初始容量Capacity对List的性能是否有影响。
测试方法：分别设置初始容量为0，64，255，1024. List插入的最大长度为1000，循环1000次，得到如下结果，单位为ms，下同。
算法/初始容量0642551024
队列35837357533717135711
堆栈302279298289
简单插入100105100100
从上面数据中我们可以看出List的初始容量对效率没有明显影响。
队列算法比较
测试方法：对LinkedList和List采用先进先出的队列算法，分别设置队列最大长度为10，30，50，100，1000，10000，并循环1000次，得到如下结果。
List类型/队列最大长度103050100100010000
LinkedList0.76590.87681.10412.040161691
List0.33261.16771.99851244337516
从测试结果中我们可以看出LinkedList 随着最大队列长度的增加，所用时间基本成线性增长。而List则成指数增长。我分析主要原因应该是每次删除List的数组头时，List都要做一次整个数数组的拷贝，而链表类型则不存在这个问题。有趣的是当队列长度小于30时，List的效率要比LinkedList要高，这主要是因为链表在增删元素时需要额外创建链表指针，而数组不需要这个操作。在队列长度较小时，这种开销就会显得很明显。
堆栈算法比较
测试方法：对LinkedList和List采用先进后出的堆栈算法，分别设置队列最大长度为10，30，50，100，1000，10000，并循环1000次，得到如下结果。
List类型/堆栈最大长度103050100100010000
LinkedList0.85150.92951.11232.187458714
List0.11090.31040.51181.225629284
从测试结果看两种类型都是线性增长，但List的性能更高一些。我分析这主要是因为List类型在增长到最大值后在从尾部删除元素，其并不重新分配内存，除非你强行让它压缩。所以List从尾部删除只是将Count改变了一下，因此效率很高。而链表类型的效率和队列方式基本相当，这也是在预料之中的，其效率比List低的原因主要还是在增删时创建和删除节点的额外开销。
简单插入算法比较
测试方法：对LinkedList和List采用向后追加若干元素的算法，分别设置插入最大长度为10，30，50，100，1000，10000，并循环1000次，得到如下结果。
List类型/插入最大长度103050100100010000
LinkedList0.67780.7650.9381.778340535
List0.08640.16610.25090.431210109
其测试结果和堆栈算法基本类似，且List的效率更高，这里不再重复论述。
总结
如果采用队列算法建议采用LinkedList类型，除非队列长度小于30.
如果采用堆栈或简单插入算法，建议采用List类型。但有一点需要说明，如果应用对内存占用有限制，建议采用LinkedList类型。
测试代码
| 以下是引用片段： class Program { const int TEST_TIMES = 1000; static private void TestQueue(int count) { TestQueue(count, 0); } static private void TestQueue(int count, int capacity) { Console.WriteLine("Count:" + count.ToString()); LinkedList linkList = new LinkedList(); List list = new List(capacity); Stopwatch watch = new Stopwatch(); watch.Start(); for (int i = 0; i < TEST_TIMES; i++) { for (int j = 0; j < count; j++) { linkList.AddLast(j); } for (int j = 0; j < count; j++) { int test = linkList.First.Value; linkList.RemoveFirst(); } } watch.Stop(); String duration; if (watch.ElapsedMilliseconds < 10) { duration = (((double)watch.ElapsedTicks) / 10000).ToString() + "ms"; } else { duration = watch.ElapsedMilliseconds.ToString() + "ms"; } Console.WriteLine("LinkedList:" + duration); watch.Reset(); watch.Start(); for (int i = 0; i < TEST_TIMES; i++) { for (int j = 0; j < count; j++) { list.Add(j); } for (int j = 0; j < count; j++) { int test = list[0]; list.RemoveAt(0); } } if (watch.ElapsedMilliseconds < 10) { duration = (((double)watch.ElapsedTicks) / 10000).ToString() + "ms"; } else { duration = watch.ElapsedMilliseconds.ToString() + "ms"; } Console.WriteLine("List:" + duration); } static private void TestStack(int count) { TestStack(count, 0); } static private void TestStack(int count, int capacity) { Console.WriteLine("Count:" + count.ToString()); LinkedList linkList = new LinkedList(); List list = new List(capacity); Stopwatch watch = new Stopwatch(); watch.Start(); for (int i = 0; i < TEST_TIMES; i++) { for (int j = 0; j < count; j++) { linkList.AddLast(j); } for (int j = 0; j < count; j++) { int test = linkList.Last.Value; linkList.RemoveLast(); } } watch.Stop(); String duration; if (watch.ElapsedMilliseconds < 10) { duration = (((double)watch.ElapsedTicks) / 10000).ToString() + "ms"; } else { duration = watch.ElapsedMilliseconds.ToString() + "ms"; } Console.WriteLine("LinkedList:" + duration); watch.Reset(); watch.Start(); for (int i = 0; i < TEST_TIMES; i++) { for (int j = 0; j < count; j++) { list.Add(j); } for (int j = 0; j < count; j++) { int test = list[list.Count-1]; list.RemoveAt(list.Count - 1); } } if (watch.ElapsedMilliseconds < 10) { duration = (((double)watch.ElapsedTicks) / 10000).ToString() + "ms"; } else { duration = watch.ElapsedMilliseconds.ToString() + "ms"; } Console.WriteLine("List:" + duration); } static private void TestInsert(int count) { TestInsert(count, 0); } static private void TestInsert(int count, int capacity) { Console.WriteLine("Count:" + count.ToString()); LinkedList linkList = new LinkedList(); List list = new List(capacity); Stopwatch watch = new Stopwatch(); watch.Start(); for (int i = 0; i < TEST_TIMES; i++) { for (int j = 0; j < count; j++) { linkList.AddLast(j); } linkList.Clear(); } watch.Stop(); String duration; if (watch.ElapsedMilliseconds < 10) { duration = (((double)watch.ElapsedTicks) / 10000).ToString() + "ms"; } else { duration = watch.ElapsedMilliseconds.ToString() + "ms"; } Console.WriteLine("LinkedList:" + duration); watch.Reset(); watch.Start(); for (int i = 0; i < TEST_TIMES; i++) { for (int j = 0; j < count; j++) { list.Add(j); } list.Clear(); } if (watch.ElapsedMilliseconds < 10) { duration = (((double)watch.ElapsedTicks) / 10000).ToString() + "ms"; } else { duration = watch.ElapsedMilliseconds.ToString() + "ms"; } Console.WriteLine("List:" + duration); } static void Main(string[] args) { //capacity TestQueue(10000, 0); TestQueue(10000, 64); TestQueue(10000, 255); TestQueue(10000, 1024); TestStack(10000, 0); TestStack(10000, 64); TestStack(10000, 255); TestStack(10000, 1024); TestInsert(10000, 0); TestInsert(10000, 64); TestInsert(10000, 255); TestInsert(10000, 1024); //compare LinkedList and List TestQueue(10); TestQueue(30); TestQueue(50); TestQueue(100); TestQueue(1000); TestQueue(10000); TestStack(10); TestStack(30); TestStack(50); TestStack(100); TestStack(1000); TestStack(10000); TestInsert(10); TestInsert(30); TestInsert(50); TestInsert(100); TestInsert(1000); TestInsert(10000); } } |