使用 List&lt;T&gt; 的性能差异是什么?vs LinkedList<T>在(c#)库中说

问题描述

可能的重复:
我应该什么时候使用 List 和 LinkedList

这个问题与我之前合并的问题有关:与List vs LinkedList

This question is related to my earlier question which was merged: related to List vs LinkedList

如果我不希望对我的数据结构使用按索引访问，那么通过使用 LinkedList 而不是 List 可以节省多少?如果不是 100% 确定我永远不会使用索引访问，我想知道其中的区别.

If I expect not to use the access by index for my data structure how much do I save by using LinkedList over List ? If if am not 100% sure I will never use access by index, I would like to know the difference.

假设我有 N 个实例.在 LinkedList 中插入和删除只会是一个 o(1) 操作，而在 List 中它可能是 O(n)，但由于它优化了，很高兴知道某些 n 值的区别是什么.假设 N = 1,000,000 和 N = 1,000,000,000

Suppose I have N instances. inserting and removing in a LinkedList will only be a o(1) op , where as in List it may me be O(n), but since it it optimized, it would be nice to know what the difference is for some values of n. say N = 1,000,000 and N = 1,000,000,000

推荐答案

好的，我做了这个实验，结果如下:

OK I did this experiment and here is the result:

这是一个包含 1000,000 个项目的列表和链表的经过时间滴答:

This is the elapsed ticks for a list and linked list with 1000,000 items:

LinkedList 500 insert/remove operations: 10171
List 500 insert/remove operations: 968465

与 1000,000 项相比，链接列表快 100 倍.

Linked list is 100 times faster when compared for 1000,000 items.

代码如下:

    static void Main(string[] args)
    {

        const int N = 1000*1000;
        Random r = new Random();
        LinkedList<int> linkedList = new LinkedList<int>();
        List<int> list = new List<int>();
        List<LinkedListNode<int>> linkedListNodes = new List<LinkedListNode<int>>();

        for (int i = 0; i < N; i++)
        {
            list.Add(r.Next());
            LinkedListNode<int> linkedListNode = linkedList.AddFirst(r.Next());
            if(r.Next() % 997 == 0)
                linkedListNodes.Add(linkedListNode);
        }

        Stopwatch stopwatch = new Stopwatch();

        stopwatch.Start();
        for (int i = 0; i < 500; i++)
        {
            linkedList.AddBefore(linkedListNodes[i], r.Next());
            linkedList.Remove(linkedListNodes[i]);
        }
        stopwatch.Stop();
        Console.WriteLine("LinkedList 500 insert/remove operations: {0}", stopwatch.ElapsedTicks);
        stopwatch.Reset();

        stopwatch.Start();
        for (int i = 0; i < 500; i++)
        {
            list.Insert(r.Next(0,list.Count), r.Next());
            list.RemoveAt(r.Next(0, list.Count));
        }
        stopwatch.Stop();
        Console.WriteLine("List 500 insert/remove operations: {0}", stopwatch.ElapsedTicks);


        Console.Read();
    }
}

这篇关于使用 List&lt;T&gt; 的性能差异是什么?vs LinkedList<T>在(c#)库中说的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！