在(c#)库中使用List <T> vs LinkedList <T>的性能差异是什么？

Question

可能重复:
我应该何时使用List vs LinkedList

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

如果我希望不通过索引访问我的数据结构,那么使用LinkedList over List可以节省多少钱？如果我不是100%肯定我永远不会使用索引访问,我想知道区别.

假设我有N个实例.在LinkedList中插入和删除将只是ao(1)op,其中在List中它可能是O(n),但由于它已经优化,因此知道n的某些值的差异会很好.比如N = 1,000,000,N = 1,000,000,000

Answer 1

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

这是包含1000,000个项目的列表和链接列表的已用刻度:

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

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

这是代码:

    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();
    }
}