List与LinkedList在使用上的性能差异是什么，比如在(c#)库中

25 浏览
0 Comments

List与LinkedList在使用上的性能差异是什么，比如在(c#)库中

这个问题已经有了答案:

可能是重复问题:

何时应该使用List还是LinkedList

这个问题与我之前的被合并的问题相关：List vs LinkedList

如果我预计不会使用下标访问我的数据结构，使用LinkedList比List能节省多少空间？如果我不确定我是否会使用下标访问，我想知道它们之间的差异。

假设我有N个实例。在LinkedList中插入和删除仅为o(1)操作，而在List中可能是O(n)操作，但由于它已经优化，我想知道某些值（如N=1,000,000和N=1,000,000,000）的区别。

admin 更改状态以发布 2023年5月24日
0

2 答案

0 Comments

不用担心。像平常一样编写你的应用程序。等它完成后，使用真实数据多次运行并对性能进行分析。替换你正在使用的类并进行结果比较。

0
0 Comments

好的，我做了这个实验，这是结果：

这是列表和链表有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 linkedList = new LinkedList();
        List list = new List();
        List> linkedListNodes = new List>();
        for (int i = 0; i < N; i++)
        {
            list.Add(r.Next());
            LinkedListNode 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();
    }
}

0