c# - 什么时候应该使用 List 和 LinkedList

Question

什么时候使用List和LinkedList更好？

score 302 · Accepted Answer

在大多数情况下，List<T>更有用。LinkedList<T>在列表中间添加/删除项目时成本会更低，而List<T>只能在列表末尾廉价添加/删除。

LinkedList<T>只有在您访问顺序数据（向前或向后）时才最有效 - 随机访问相对昂贵，因为它每次都必须遍历链（因此它没有索引器）。但是，因为 aList<T>本质上只是一个数组（带有包装器），所以随机访问是可以的。

List<T>还提供了很多支持方法—— Find、、ToArray等；但是，这些也可用于LinkedList<T>.NET 3.5/C# 3.0 通过扩展方法 - 所以这不是一个因素。

score 239 · Accepted Answer

将链接列表视为列表可能有点误导。它更像是一条链子。事实上，在 .NET 中，LinkedList<T>甚至没有实现IList<T>. 链表中没有真正的索引概念，即使看起来有。当然，类上提供的方法都不接受索引。

链表可以是单链的，也可以是双链的。这是指链中的每个元素是否仅与下一个元素（单链接）或前一个/下一个元素（双重链接）有链接。 LinkedList<T>是双重联系的。

在内部，List<T>由数组支持。这在内存中提供了非常紧凑的表示。相反，LinkedList<T>涉及额外的内存来存储连续元素之间的双向链接。因此 a 的内存占用LinkedList<T>通常会大于 for List<T>（需要注意的是，List<T>可以使用未使用的内部数组元素来提高附加操作期间的性能。）

它们也具有不同的性能特征：

附加

LinkedList<T>.AddLast(item) 恒定时间
List<T>.Add(item) 摊销常数时间，线性最坏情况

前置

LinkedList<T>.AddFirst(item) 恒定时间
List<T>.Insert(0, item) 线性时间

插入

LinkedList<T>.AddBefore(node, item) 恒定时间
LinkedList<T>.AddAfter(node, item) 恒定时间
List<T>.Insert(index, item) 线性时间

移动

LinkedList<T>.Remove(item) 线性时间
LinkedList<T>.Remove(node) 恒定时间
List<T>.Remove(item) 线性时间
List<T>.RemoveAt(index) 线性时间

数数

LinkedList<T>.Count 恒定时间
List<T>.Count 恒定时间

包含

LinkedList<T>.Contains(item) 线性时间
List<T>.Contains(item) 线性时间

清除

LinkedList<T>.Clear() 线性时间
List<T>.Clear() 线性时间

如您所见，它们大多是等价的。在实践中，APILinkedList<T>使用起来更加麻烦，并且其内部需求的细节会溢出到您的代码中。

但是，如果您需要从列表中进行多次插入/删除，它会提供恒定的时间。 List<T>提供线性时间，因为列表中的额外项目必须在插入/删除后随机播放。

score 118 · Accepted Answer

链表提供非常快速的列表成员插入或删除。链表中的每个成员都包含指向链表中下一个成员的指针，以便在位置 i 插入成员：

更新成员 i-1 中的指针以指向新成员
将新成员中的指针设置为指向成员 i

链表的缺点是无法进行随机访问。访问成员需要遍历列表，直到找到所需的成员。

score 111 · Accepted Answer

编辑

请阅读对此答案的评论。人们声称我没有进行适当的测试。我同意这不应该是一个公认的答案。在我学习的过程中，我做了一些测试，并想分享它们。

原答案...

我发现了有趣的结果：

// Temporary class to show the example
class Temp
{
    public decimal A, B, C, D;

    public Temp(decimal a, decimal b, decimal c, decimal d)
    {
        A = a;            B = b;            C = c;            D = d;
    }
}

链表（3.9 秒）

        LinkedList<Temp> list = new LinkedList<Temp>();

        for (var i = 0; i < 12345678; i++)
        {
            var a = new Temp(i, i, i, i);
            list.AddLast(a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

列表（2.4 秒）

        List<Temp> list = new List<Temp>(); // 2.4 seconds

        for (var i = 0; i < 12345678; i++)
        {
            var a = new Temp(i, i, i, i);
            list.Add(a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

即使您基本上只访问数据，它也会慢得多！！我说永远不要使用linkedList。

这是另一个执行大量插入的比较（我们计划在列表中间插入一个项目）

链表（51 秒）

        LinkedList<Temp> list = new LinkedList<Temp>();

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.AddLast(a);
            var curNode = list.First;

            for (var k = 0; k < i/2; k++) // In order to insert a node at the middle of the list we need to find it
                curNode = curNode.Next;

            list.AddAfter(curNode, a); // Insert it after
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

列表（7.26 秒）

        List<Temp> list = new List<Temp>();

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.Insert(i / 2, a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

链接列表具有插入位置的参考（0.04 秒）

        list.AddLast(new Temp(1,1,1,1));
        var referenceNode = list.First;

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.AddLast(a);
            list.AddBefore(referenceNode, a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

因此，只有当您计划插入多个项目并且您在某个地方也有您计划插入项目的参考时，然后才使用链表。仅仅因为您必须插入很多项目并不能使其更快，因为搜索您要插入的位置需要时间。

score 38 · Accepted Answer

我之前的回答不够准确。确实这太可怕了：D但现在我可以发布更多有用和正确的答案。

我做了一些额外的测试。您可以通过以下链接找到它的源代码并自行在您的环境中重新检查它：https ://github.com/ukushu/DataStructuresTestsAndOther.git

简短的结果：

数组需要使用：
- 尽可能经常。它速度很快，并且对于相同数量的信息占用最小的 RAM 范围。
- 如果您知道所需细胞的确切数量
- 如果保存在数组中的数据 < 85000 b（整数数据为 85000/32 = 2656 个元素）
- 如果需要高随机存取速度
清单需要使用：
- 如果需要将单元格添加到列表末尾（经常）
- 如果需要在列表的开头/中间添加单元格（不经常）
- 如果保存在数组中的数据 < 85000 b（整数数据为 85000/32 = 2656 个元素）
- 如果需要高随机存取速度
LinkedList 需要使用：
- 如果需要在列表的开头/中间/结尾添加单元格（经常）
- 如果需要仅顺序访问（向前/向后）
- 如果您需要保存 LARGE 项目，但项目数量很少。
- 最好不要用于大量项目，因为它会为链接使用额外的内存。

更多细节：

有趣的是：

LinkedList<T>在内部不是 .NET 中的列表。它甚至没有实现IList<T>。这就是为什么没有索引和与索引相关的方法的原因。
LinkedList<T>是基于节点指针的集合。在 .NET 中，它是双向链接的实现。这意味着先前/下一个元素具有指向当前元素的链接。并且数据是碎片化的——不同的列表对象可以位于 RAM 的不同位置。也将有LinkedList<T>比 forList<T>或 Array 更多的内存使用。
List<T>在 .Net 中是 Java 的ArrayList<T>. 这意味着这是数组包装器。所以它作为一个连续的数据块在内存中分配。如果分配的数据大小超过 85000 字节，它将被移动到大对象堆。根据大小，这可能会导致堆碎片（一种温和的内存泄漏形式）。但同时如果 size < 85000 字节——这在内存中提供了一个非常紧凑和快速访问的表示。
单个连续块对于随机访问性能和内存消耗是首选，但对于需要定期更改大小的集合，通常需要将诸如 Array 之类的结构复制到新位置，而链表只需要管理新插入的内存/删除的节点。

score 20 · Accepted Answer

List 和 LinkedList 的区别在于它们的底层实现。List 是基于数组的集合（ArrayList）。LinkedList 是基于节点指针的集合 (LinkedListNode)。在 API 级别的使用上，它们几乎相同，因为它们都实现了相同的接口集，例如 ICollection、IEnumerable 等。

当性能很重要时，关键的区别就出现了。例如，如果您正在实现具有大量“INSERT”操作的列表，则 LinkedList 优于 List。由于 LinkedList 可以在 O(1) 时间内完成，但 List 可能需要扩展底层数组的大小。有关更多信息/详细信息，您可能需要阅读 LinkedList 和数组数据结构之间的算法差异。http://en.wikipedia.org/wiki/Linked_list和数组

希望这有帮助，

score 12 · Accepted Answer

与数组相比，链表的主要优点是链接为我们提供了有效地重新排列项目的能力。塞奇威克，p。91

score 4 · Accepted Answer

使用 LinkedList 的常见情况是这样的：

假设你想从一个很大的字符串列表中删除许多特定的字符串，比如 100,000。要删除的字符串可以在 HashSet dic 中查找，并且字符串列表被认为包含 30,000 到 60,000 个要删除的此类字符串。

那么存储 100,000 个字符串的最佳 List 类型是什么？答案是链表。如果它们存储在 ArrayList 中，则对其进行迭代并删除匹配的字符串可能需要数十亿次操作，而使用迭代器和 remove() 方法只需要大约 100,000 次操作。

LinkedList<String> strings = readStrings();
HashSet<String> dic = readDic();
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()){
    String string = iterator.next();
    if (dic.contains(string))
    iterator.remove();
}

score 2 · Accepted Answer

当您需要内置索引访问、排序（以及在此二进制搜索之后）和“ToArray()”方法时，您应该使用 List。

score 2 · Accepted Answer

本质上，List<>.NET 中的 a 是数组的包装器。ALinkedList<> 是一个链表。所以问题归结为，数组和链表有什么区别，什么时候应该使用数组而不是链表。您决定使用哪个最重要的因素可能归结为：

链表具有更好的插入/删除性能，只要插入/删除不在集合中的最后一个元素上。这是因为数组必须移动插入/删除点之后的所有剩余元素。但是，如果插入/删除位于列表的末尾，则不需要这种移位（尽管如果超出了数组的容量，可能需要调整数组的大小）。
数组具有更好的访问能力。数组可以直接索引（在恒定时间内）。必须遍历链表（线性时间）。

score 1 · Accepted Answer

这是改编自Tono Nam接受的答案，纠正了其中的一些错误测量。

考试：

static void Main()
{
    LinkedListPerformance.AddFirst_List(); // 12028 ms
    LinkedListPerformance.AddFirst_LinkedList(); // 33 ms

    LinkedListPerformance.AddLast_List(); // 33 ms
    LinkedListPerformance.AddLast_LinkedList(); // 32 ms

    LinkedListPerformance.Enumerate_List(); // 1.08 ms
    LinkedListPerformance.Enumerate_LinkedList(); // 3.4 ms

    //I tried below as fun exercise - not very meaningful, see code
    //sort of equivalent to insertion when having the reference to middle node

    LinkedListPerformance.AddMiddle_List(); // 5724 ms
    LinkedListPerformance.AddMiddle_LinkedList1(); // 36 ms
    LinkedListPerformance.AddMiddle_LinkedList2(); // 32 ms
    LinkedListPerformance.AddMiddle_LinkedList3(); // 454 ms

    Environment.Exit(-1);
}

和代码：

using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace stackoverflow
{
    static class LinkedListPerformance
    {
        class Temp
        {
            public decimal A, B, C, D;

            public Temp(decimal a, decimal b, decimal c, decimal d)
            {
                A = a; B = b; C = c; D = d;
            }
        }



        static readonly int start = 0;
        static readonly int end = 123456;
        static readonly IEnumerable<Temp> query = Enumerable.Range(start, end - start).Select(temp);

        static Temp temp(int i)
        {
            return new Temp(i, i, i, i);
        }

        static void StopAndPrint(this Stopwatch watch)
        {
            watch.Stop();
            Console.WriteLine(watch.Elapsed.TotalMilliseconds);
        }

        public static void AddFirst_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Insert(0, temp(i));

            watch.StopAndPrint();
        }

        public static void AddFirst_LinkedList()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (int i = start; i < end; i++)
                list.AddFirst(temp(i));

            watch.StopAndPrint();
        }

        public static void AddLast_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Add(temp(i));

            watch.StopAndPrint();
        }

        public static void AddLast_LinkedList()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (int i = start; i < end; i++)
                list.AddLast(temp(i));

            watch.StopAndPrint();
        }

        public static void Enumerate_List()
        {
            var list = new List<Temp>(query);
            var watch = Stopwatch.StartNew();

            foreach (var item in list)
            {

            }

            watch.StopAndPrint();
        }

        public static void Enumerate_LinkedList()
        {
            var list = new LinkedList<Temp>(query);
            var watch = Stopwatch.StartNew();

            foreach (var item in list)
            {

            }

            watch.StopAndPrint();
        }

        //for the fun of it, I tried to time inserting to the middle of 
        //linked list - this is by no means a realistic scenario! or may be 
        //these make sense if you assume you have the reference to middle node

        //insertion to the middle of list
        public static void AddMiddle_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Insert(list.Count / 2, temp(i));

            watch.StopAndPrint();
        }

        //insertion in linked list in such a fashion that 
        //it has the same effect as inserting into the middle of list
        public static void AddMiddle_LinkedList1()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            LinkedListNode<Temp> evenNode = null, oddNode = null;
            for (int i = start; i < end; i++)
            {
                if (list.Count == 0)
                    oddNode = evenNode = list.AddLast(temp(i));
                else
                    if (list.Count % 2 == 1)
                        oddNode = list.AddBefore(evenNode, temp(i));
                    else
                        evenNode = list.AddAfter(oddNode, temp(i));
            }

            watch.StopAndPrint();
        }

        //another hacky way
        public static void AddMiddle_LinkedList2()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start + 1; i < end; i += 2)
                list.AddLast(temp(i));
            for (int i = end - 2; i >= 0; i -= 2)
                list.AddLast(temp(i));

            watch.StopAndPrint();
        }

        //OP's original more sensible approach, but I tried to filter out
        //the intermediate iteration cost in finding the middle node.
        public static void AddMiddle_LinkedList3()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
            {
                if (list.Count == 0)
                    list.AddLast(temp(i));
                else
                {
                    watch.Stop();
                    var curNode = list.First;
                    for (var j = 0; j < list.Count / 2; j++)
                        curNode = curNode.Next;
                    watch.Start();

                    list.AddBefore(curNode, temp(i));
                }
            }

            watch.StopAndPrint();
        }
    }
}

您可以看到结果与其他人在此处记录的理论性能一致。非常清楚 -LinkedList<T>在插入的情况下获得大量时间。我还没有测试从列表中间删除，但结果应该是一样的。当然List<T>还有其他领域表现得更好，比如 O(1) 随机访问。

score 0 · Accepted Answer

LinkedList<>何时使用

你不知道有多少物体正在通过防洪闸门。例如，Token Stream。
当您只想在末尾删除\插入时。

对于其他一切，最好使用List<>.

score 0 · Accepted Answer

我同意上面提出的大部分观点。而且我也同意 List 在大多数情况下看起来是一个更明显的选择。

但是，我只想补充一点，在很多情况下，LinkedList 比 List 更好，效率更高。

假设您正在遍历元素并且想要执行大量插入/删除；LinkedList 在线性 O(n) 时间内完成，而 List 在二次 O(n^2) 时间内完成。
假设你想一次又一次地访问更大的对象，LinkedList 变得非常有用。
使用 LinkedList 更好地实现 Deque() 和 queue()。
一旦您处理许多更大的对象，增加 LinkedList 的大小会更容易和更好。

希望有人会发现这些评论有用。

score -2 · Accepted Answer

在 .NET 中，列表表示为数组。因此，与 LinkedList 相比，使用普通 List 会更快。这就是上面的人看到他们看到的结果的原因。

为什么要使用列表？我会说这取决于。如果您没有指定任何元素，List 会创建 4 个元素。当你超过这个限制时，它会将内容复制到一个新数组中，将旧数组留在垃圾收集器的手中。然后它的大小加倍。在这种情况下，它会创建一个包含 8 个元素的新数组。想象一下有一个包含 100 万个元素的列表，然后再添加 1 个。它本质上将创建一个全新的数组，其大小是您需要的两倍。新阵列将具有 2Mil 容量，但是您只需要 1Mil 和 1。基本上将 GEN2 中的东西留给垃圾收集器等等。所以它实际上最终可能成为一个巨大的瓶颈。你应该对此小心。

score -3 · Accepted Answer

我问了一个与 LinkedList 集合性能相关的类似问题，发现Steven Cleary 的 Deque 的 C# 实现是一个解决方案。与 Queue 集合不同，Deque 允许前后移动项目。它类似于链表，但性能有所提高。