何时应该使用List而不是LinkedList？

Question

何时更适合使用 List 而不是 LinkedList？

- Grauenwolf

---

当需要频繁地在列表的中间位置进行插入和删除操作时，应该使用LinkedList而不是ArrayList。 - nawfal

@jonathan-allen，请考虑更改已接受的答案。当前答案不准确且极其误导。 - Xpleria

正如Xpleria所说，请考虑更改当前被接受的答案。目前的答案是误导性的。 - Leonardo

Answer 1

在大多数情况下，List<T>更有用。当添加/删除列表中间的项目时，LinkedList<T>的成本较低，而List<T>只能在列表末尾轻松添加/删除。 LinkedList<T>仅在访问顺序数据（向前或向后）时达到最高效率——随机访问相对昂贵，因为每次都必须遍历链表（因此它没有索引器）。然而，由于List<T>本质上只是一个数组（带有包装器），所以随机访问很好。 List<T>还提供了许多支持方法，例如Find、ToArray等。然而，通过.NET 3.5/C# 3.0的扩展方法，这些方法也可用于LinkedList<T>，因此这不是一个重要因素。

- Marc Gravell

---

List<> 相对于 LinkedList<> 的一个优点是，我之前从未想到过，它涉及微处理器如何实现内存缓存。尽管我并不完全理解，但这篇博客文章的作者谈到了“引用局部性”，这使得遍历数组比遍历链表要快得多，至少在链表在内存中变得有些分散的情况下是如此。链接：http://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/ - RenniePet

由于List是动态数组，因此如果您事先知道容量的话，有时在构造函数中指定List的容量是一个好习惯。 - Cardin

C#中的所有、数组、List<T>和LinkedList<T>实现在一个非常重要的情况下可能有些次优：您需要一个非常大的列表，追加（AddLast）和顺序遍历（单向）完全没有问题：我不想要数组调整大小以获得连续块（即使是20 GB的数组，这是否保证每个数组都是连续的？），而且我事先不知道大小，但我可以预测每次预留的块大小，例如100 MB。这将是一个很好的实现。或者数组/列表类似于此，并且我错过了一点吗？ - Philm

@Philm 这种情况下，你需要编写自己的 shim 以覆盖所选块策略；List<T> 和 T[] 太过笨重（全部在一个块中），而 LinkedList<T> 则因为每个元素都有一个块而过于细粒度。 - Marc Gravell

是的。同时我正在考虑实现一个LinkedList<T>的数组shim，大小为10MB或者其他什么。这个实现可能会很有趣。 - Philm

Answer 2

将链表看作一个列表可能会有点误导。它更像是一条链。事实上，在 .NET 中，LinkedList<T> 甚至没有实现 IList<T> 接口。链表中没有真正的索引概念，尽管看起来似乎有。当然，这个类提供的方法中没有接受索引参数的。

链表可以是单向的，也可以是双向的。这指的是每个元素在链中只有指向下一个元素的链接（单向链接），还是同时有指向前一个和后一个元素的链接（双向链接）。LinkedList<T> 是双向链接的。

在内部，List<T> 使用数组作为其支持。这提供了一种非常紧凑的内存表示方式。相反，LinkedList<T> 需要额外的内存来存储相邻元素之间的双向链接。因此，LinkedList<T> 的内存占用通常会比 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() 线性时间

可以看出，它们大多数是等价的。实际上，LinkedList<T> 的API使用起来更加繁琐，并且其内部细节会泄漏到您的代码中。

但是，如果您需要在列表内进行多次插入/删除操作，它可以提供常数时间。而List<T>则需要线性时间，因为插入/删除后必须重新排列列表中的额外项。

- Drew Noakes

---

链表的计数是常数时间吗？我以为是线性时间？ - Iain Ballard

@Iain，计数在这两个列表类中都被缓存了。 - Drew Noakes

您写道 "List<T>.Add(item) 的时间复杂度是对数级别"，但实际上如果列表容量足够存储新项，则其时间复杂度为 "常数级别"，如果列表没有足够的空间并需要重新分配，则时间复杂度为 "线性级别"。 - aStranger

我在某些结论中看到了一个矛盾：假设我只关心Append的速度，那么什么最好？我想用一些百万行文本行（或任何其他流）填充容器，但我不关心RAM：我只需要关心Append的速度（.添加到列表的末尾）。这是最重要的（规范）情况，插入到中间是另一回事：-----使用LinkedList<T>还是List<T>更好？ - Philm

@Philm，你可能应该开始一个新的问题，并且你没有说一下在构建这个数据结构后你将如何使用它，但如果你要处理一百万行数据，你可能会喜欢一些混合型的数据结构（例如链表数组块等），以减少堆碎片、降低内存开销，并避免在LOH上创建单个巨大对象。 - Drew Noakes

Answer 3

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

• 更新成员 i-1 中的指针，使其指向新成员
• 设置新成员中的指针，使其指向成员 i

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

- b3

---

我认为需要补充一点，就是链表每存储一个项就会增加额外的开销，这是通过LinkedListNode来实现的，它引用了前一个和后一个节点。但好处是，不像基于数组的列表，链表不需要连续的内存块来存储。 - paulecoyote

通常情况下，连续的内存块更受青睐吗？ - Jonathan Allen

是的，对于需要随机访问和内存消耗的连续块是首选，但对于需要经常改变大小的集合，如数组这样的结构通常需要被复制到新位置，而链表只需要管理新插入/删除节点的内存。 - jpierson

如果您曾经需要使用非常大的数组或列表进行工作（列表只是封装了一个数组），即使您的计算机上似乎有足够的内存，您也会开始遇到内存问题。列表在分配其基础数组中的新空间时使用加倍策略。因此，一个已满的1000000元素数组将被复制到一个具有2000000个元素的新数组中。这个新数组需要在足够大的连续内存空间中创建。 - Andrew

如果将双向链表与字典相结合，您可以在插入/删除和访问时获得O（1）速度。 - ALZ

Answer 4

编辑

请阅读此回答下方的评论。有人声称我没有进行适当的测试。我同意这不应该是一个被接受的答案。在学习过程中，我进行了一些测试并决定分享它们。

原始回答...

我发现了一些有趣的结果：

// 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;

即使你只是基本访问数据，也会慢得多!! 我建议永远不要使用链表。

---

---

---

这里是另一个比较，在执行大量插入操作时（我们计划在列表中间插入一个项）

链表（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;

带有插入位置引用的链表（.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;

所以只有在您计划插入多个项目并且同时有要插入项目的位置参考时，才使用链表。仅仅因为您需要插入许多项目，并不意味着它会更快，因为查找要插入的位置需要时间。

- Tono Nam

---

LinkedList比List（这是.NET特定的）有一个好处：由于List由内部数组支持，因此它被分配在一个连续的块中。如果分配的块大小超过85000字节，则将在大对象堆上分配它，这是一个不可压缩的代。根据大小，这可能导致堆碎片化，一种轻微的内存泄漏形式。 - JerKimball

请注意，如果您添加的项很多（就像在最后一个例子中所做的那样），或者删除了第一个条目，则链表几乎总是比List更快，因为不需要搜索或移动/复制任何内容。 List将需要将所有内容向上移动一个位置以容纳新项，使添加到开头成为O（N）操作。 - cHao

为什么在最后两个 LinkedList 的示例中，循环中要使用 list.AddLast(a);？我知道在循环之前添加一次，就像在倒数第二个 LinkedList 中使用 list.AddLast(new Temp(1,1,1,1)); 一样，但是在循环本身中似乎会添加两倍于所需的 Temp 对象。（当我用一个测试应用程序进行自我检查时，LinkedList 中确实有两倍数量的对象。） - ruffin

我对这个答案进行了负评。1）你的普遍建议“我说永远不要使用链表”是有缺陷的，因为你随后的帖子揭示了这一点，你可能需要编辑它。2）你正在计时什么？实例化、添加和枚举都在一个步骤中吗？通常，实例化和枚举不是人们担心的问题，那些是一次性的步骤。具体计时插入和添加会给出更好的想法。3）最重要的是，你向链表中添加了比所需更多的内容。这是错误的比较。传递了关于链表错误的想法。 - nawfal

抱歉，但这个答案真的很糟糕。请不要听从这个答案。简而言之，认为基于数组的列表实现每次插入都会重新调整大小是完全错误的。与链表相比，基于数组的列表在遍历以及在两端插入时自然会更快，因为它们只需要创建新的对象，而基于数组的列表则使用缓冲区（显然是双向的）。这些（做得很差的）基准测试正是指出这一点的。这个答案完全没有检查链表更适合的情况！ - mafu

Answer 5

我的上一个回答不够准确。

事实上，它是可怕的 :D

但现在我可以发布更有用和正确的答案了。

---

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

短期成果：

• 需要使用数组：
• 尽可能经常使用。 它快速且占用的 RAM 范围最小，以存储相同数量的信息。
• 如果您知道所需单元格的确切数量
• 如果数据保存在数组中且＜85000 b（整数数据的 85000/32 = 2656 个元素）
• 如果需要高速随机访问
• 需要使用列表：
• 如果需要将单元格添加到列表末尾（经常）
• 如果需要在列表开头/中间添加单元格（不经常）
• 如果数据保存在数组中且＜85000 b（整数数据的 85000/32 = 2656 个元素）
• 如果需要高速随机访问
• 需要使用 LinkedList：
• 如果需要经常在列表开头/中间/结尾添加单元格
• 如果仅需要连续访问（向前/向后）
• 如果要保存大型项，但项数较少。
• 不要将其用于大量项目，因为它会使用额外的内存来存储链接。

更多细节：

有趣的是：

1. LinkedList<T>在.NET中内部不是一个列表。它甚至没有实现IList<T>。这就是为什么缺少索引和与索引相关的方法。

2. LinkedList<T>是基于节点指针的集合，在.NET中它是双向链表实现。这意味着前/后元素有链接到当前元素。数据是分散的--不同的列表对象可以位于RAM的不同位置。此外，LinkedList<T>使用的内存比List<T>或数组更多。

3. List<T>在.NET中是Java的替代ArrayList<T>。这意味着这是一个数组包装器。因此，它作为一块连续的数据块在内存中分配。如果分配的数据大小超过85000字节，则会将其移动到大型对象堆。根据大小，这可能导致堆片段（一种轻微的内存泄漏）。但同时，如果大小小于85000字节，则提供了非常紧凑和快速访问内存中的表示。

4. 单个连续块对于随机访问性能和内存消耗的性能更佳，但是对于需要定期更改大小的集合，诸如数组之类的结构通常需要复制到新位置，而链表仅需要管理新插入/删除节点的内存。

- Andrew___Pls_Support_UA

---

问题：您所说的“数据保存在数组<或> 85,000字节”是指每个数组/列表元素的数据吗？这可能被理解为您指的是整个数组的数据大小。 - Philm

数组元素按顺序存储在内存中。每个数组都是如此。我知道表格上有错误，稍后我会修复它 :) （希望……） - Andrew_STOP_RU_WAR_IN_UA

由于列表在插入时速度较慢，如果一个列表有很多的操作(大量的插入/删除)，那么被删除空间所占用的内存是否会被保留，如果是的话，这是否会使重新插入更快？ - Rob

如果数据保存在数组中<85000 b（85000/32 = 2656个整数数据元素），您是指85000位还是字节？我假设整数占用4个字节，而不是32个。 - olegz

Answer 6

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

关键的区别在于性能问题。例如，如果您正在实现具有大量“插入”操作的列表，LinkedList比List更为优越。因为LinkedList可以在O(1)时间内完成，但List可能需要扩展底层数组的大小。如需了解更多信息/详细信息，您可能需要阅读LinkedList和数组数据结构之间算法差异的相关资料。可参考链接：http://en.wikipedia.org/wiki/Linked_list和Array

希望这可以帮助您，

- user23117

---

List<T> 基于数组（T[]），而不是基于 ArrayList。重新插入时，数组的大小调整不是问题（因为倍增算法意味着大多数情况下不需要这样做）：问题在于它必须先阻止复制所有现有数据，这需要一些时间。 - Marc Gravell

@Marc，"倍增算法"只能将其复杂度降至O(logN)，但仍然比O(1)差。 - Ilya Ryzhenkov

我的观点是，引起疼痛的不是调整大小，而是 blit。因此，最坏的情况是，如果我们每次都添加第一个（零）元素，则 blit 必须每次移动所有内容。 - Marc Gravell

@IlyaRyzhenkov - 你正在考虑Add总是在现有数组的末尾的情况。即使不是O(1)，List也足够好。严重的问题出现在需要许多不在末尾的Add的情况下。Marc指出，每次插入时（不仅在需要调整大小时）需要移动现有数据是List更实质性的性能成本。 - ToolmakerSteve

问题在于理论上的大O符号并不能讲述整个故事。在计算机科学中，这是所有人关心的唯一问题，但在现实世界中，还有更多需要关注的问题。 - MattE

Answer 7

链表相较于数组的主要优点在于它们提供了链接来有效地重新排列项目的能力。

- Dr. Alrawi

---

在我看来，这应该是答案。当保证顺序很重要时，LinkedList 就会被使用。 - RBaarda

@RBaarda：我不同意。这取决于我们所讨论的级别。算法级别与机器实现级别是不同的。出于速度考虑，您也需要后者。正如指出的那样，数组被实现为“一块”内存，这是一种限制，因为这可能会导致调整大小和内存重新组织，特别是对于非常大的数组。经过一段时间的思考，一个特殊的自有数据结构，即数组的链表，将是一个想法，以便更好地控制线性填充和访问非常大的数据结构的速度。 - Philm

@Philm - 我点赞了你的评论，但我想指出你描述的是另一个需求。回答中所说的是链表在涉及大量重新排列项目的算法中具有性能优势。鉴于此，我理解RBaarda的评论是指需要添加/删除项目并同时不断维护给定排序（排序标准）。因此不仅仅是“线性填充”。在这种情况下，List会失去优势，因为索引是无用的（除非您只在尾端添加元素）。 - ToolmakerSteve

@RBaarda 不，这不应该是答案，它只是复制粘贴了一个参考资料，没有提供示例或自己的输入。最好的做法是留下评论而不是答案。 - Farid

Answer 8

使用LinkedList的一个常见情况如下：

假设您想从一个包含大量字符串（比如10万个）的字符串列表中删除许多特定的字符串。要删除的字符串可以在HashSet字典中查找，而字符串列表被认为包含30,000到60,000个这样的字符串。

那么用什么类型的List来存储这100,000个字符串呢？答案是LinkedList。如果它们存储在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();
}

- Tom

---

您可以使用 RemoveAll 简单地从 List 中移除项目而无需大量移动项目，或者使用 LINQ 中的 Where 创建第二个列表。然而，在这里使用 LinkedList 将会消耗显著更多的内存比其他类型的集合，并且由于失去了内存局部性，迭代速度明显变慢，使它比 List 差得多。 - Servy

@Servy，请注意@Tom的答案使用Java。我不确定Java中是否有RemoveAll的相应方法。 - Arturo Torres Sánchez

好的，这道题明确指出是关于.NET的，因此这使得答案更不合适了。 - Servy

@Servy，那么你应该从一开始就提到这个。 - Arturo Torres Sánchez

如果List没有提供RemoveAll方法，你可以使用“压缩”算法，它看起来像Tom的循环，但有两个索引，并且需要将要保留的项逐个向下移动到列表的内部数组中。效率为O(n)，与LinkedList的Tom算法相同。在两个版本中，计算字符串的HashSet键的时间占主导地位。这不是使用LinkedList的好例子。 - ToolmakerSteve

Answer 9

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

- Michael Damatov

Answer 10

基本上，.NET中的List<>是对数组的封装。而LinkedList<>则是一个链表。所以问题就在于，数组和链表之间有什么区别，何时应该使用数组而不是链表。你决定使用哪个的最重要的两个因素可能是：

• 如果插入/删除操作不在集合的最后一个元素上，那么链表具有更好的插入/删除性能。这是因为数组必须将插入/删除点之后的所有剩余元素移动。但是，如果插入/删除在列表的末尾，则不需要进行此移动（尽管如果超出其容量，数组可能需要调整大小）。
• 数组具有更好的访问能力。可以直接对数组进行索引（在常数时间内）。而要遍历链表（线性时间）。

- John Smith