学步园

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

.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的效率更高，这里不再重复论述。

 

总结

如果采用队列算法建议采用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<int> linkList = new LinkedList<int>();
            List<int> list = new List<int>(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());