何时使用链表而不是数组/数组列表？

Question

我使用了很多列表和数组，但我还没有遇到过一个场景，在这个场景中，链表比起数组列表来说能更容易地被使用，或者说更加优越。我希望有人能给我一些示例，说明何时使用链表会更加明显优于使用数组列表。

- faceless1_14

---

在Java中，ArrayList和LinkedList使用的代码完全相同，除了构造函数。你所说的"数组列表可以像链表一样容易地或更容易地使用"是没有意义的。请提供一个ArrayList比LinkedList更易用的示例。 - S.Lott

请查看以下链接：https://dev59.com/Y3RC5IYBdhLWcg3wW_tk#24607151 - NoNaMe

可能是数组与链表的重复问题。 - Hawkeye Parker

那不是真的。Java的ArrayList是围绕数组包装的，并添加了一些实用函数。而链表显然是链表。http://developer.classpath.org/doc/java/util/ArrayList-source.html - kingfrito_5005

Answer 1

链表在以下情况下优于数组：

1. 需要常数时间的列表插入/删除（例如在实时计算中，时间可预测性非常关键）

2. 不知道列表中会有多少项。使用数组时，如果数组变得太大，可能需要重新声明和复制内存。

3. 不需要任何元素的随机访问

4. 要能够在列表中间插入项目（例如优先级队列）

数组在以下情况下优于链表：

1. 需要对元素进行索引/随机访问

2. 预先知道数组中元素的数量，以便可以为数组分配正确数量的内存

3. 需要迭代按顺序遍历所有元素时速度更快。您可以在数组上使用指针数学来访问每个元素，而在链表中，您需要基于指针查找每个元素的节点，这可能导致页面故障，从而影响性能。

4. 关注内存。填充的数组比链接列表占用更少的内存。数组中的每个元素只是数据。每个链表节点都需要数据以及指向链接列表中其他元素的一个或多个指针。

数组列表（例如 .Net 中的ArrayList）使您可以获得数组的好处，但动态为您分配资源，因此您不需要太担心列表大小，而且可以轻松删除任何索引处的项目或重新排列元素。从性能上讲，数组列表比原始数组慢。

- Lamar

---

起步不错，但这遗漏了重要内容：列表支持结构共享，数组更密集且具有更好的局部性。 - Darius Bacon

自从 LinkedList 什么时候拥有 O(1) 的插入/删除操作了（当你说“常数时间插入/删除”时，我想你指的就是这个）？在 LinkedList 中插入元素到中间位置始终是 O(n)。 - Pacerier

如果你已经通过迭代器到达插入位置，链表的插入操作的时间复杂度可以达到O(1)，但并非总是如此。 - Adam

使用链表来实现优先队列是一个非常愚蠢的想法。动态数组支持的堆允许在摊销意义下进行O(lg n)的插入操作，在最坏情况下以对数时间复杂度进行delete-min，是最快的实用优先队列结构之一。 - Fred Foo

@Lamar，你能给我举一个常数时间插入/删除的实际例子吗？我不是很理解。 - İsmail Kocacan

Answer 2

• 数组具有 O(1) 的随机访问能力，但在添加或移除元素时的成本非常高。

• 链表添加或删除任意位置的元素和迭代都非常便宜，但随机访问的成本为O(n)。

- Dustin

---

从数组末尾删除项是常数时间操作，从链表的任一端插入/删除项也是常数时间操作。但是在链表中间进行插入/删除操作则不是这样。 - Joey

@Joey在链表末尾进行插入/删除不是O(n)吗？除非您已经位于倒数第二个链接，否则仍需要O(n)步骤才能找到最后一个元素，对吧？ - Alex Moore-Niemi

@AlexMoore-Niemi：对于单向链表是这样的。但是许多链表都有前后链接，因此会保留指向两端的指针。 - Joey

如果你有一个双向链表，就会让你前后搜索，除非你的链表有排序过的值...但即使是最坏情况，时间复杂度也是O(n)。 - securecurve

“链表非常便宜，可以在任何地方添加或删除项目并进行迭代”这种说法并不完全正确。如果我想要删除链表中间的一个项目，我必须从开头开始迭代，直到到达该项目所在的位置。这需要O(n/2)的时间，其中n是列表中的项目数。从你的回答中听起来，你似乎在暗示它是常数时间O(1)，就像数组一样。但是，从链表的头/根节点添加/删除是常数时间。 - Yawar Murtaza

链表实际上是相当耗费的迭代操作。在内存中遍历所有这些指针会完全破坏缓存局部性。 - Deduplicator

Answer 3

Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

ArrayList（数组列表）适用于写一次读多次或者追加操作，但在从头部或中间添加/删除操作上表现较差。

- Vpn_talent

---

请注意，仅当您已经拥有指向要插入新节点的元素之后的指针时，才能在链表中插入元素的时间复杂度为O(1)。否则，您将不得不迭代链表直到找到正确的位置，这将是O(N)。 - Ricky Sixx

相信只有在有可用的索引时，ArrayList末尾插入的时间复杂度才是O(1)。如果没有可用的位置，则需要调整数组大小并复制现有元素，这将花费O(n)的时间。 - Matthew

在链表中插入一个元素（简单地说“插入”）的时间复杂度是O(n)，而不是O(1)！ - Arashsyh

Answer 4

除了其他回答所述，大多数数组列表实现在列表末尾保留额外的容量，以便可以在O(1)时间内向列表末尾添加新元素。当数组列表的容量超过限制时，内部会分配一个新的、更大的数组，并将所有旧元素复制到其中。通常，新数组的大小是旧数组的两倍。这意味着，在这些实现中，平均而言，向数组列表末尾添加新元素是一个O(1)操作。因此，即使您不知道元素的数量，只要您在末尾添加它们，数组列表可能仍然比链表更快。显然，在任意位置插入新元素到数组列表仍然是一个O(n)操作。

即使访问是顺序的，访问数组列表中的元素也比访问链表更快。这是因为数组元素存储在连续的内存中，很容易被缓存。链表节点可能散布在许多不同的页面上。

我建议只在您知道将在任意位置插入或删除项目时才使用链表。对于几乎所有其他情况，数组列表都会更快。

- Jay

---

此外，您还可以使用动态数组实现链表（在抽象数据类型意义上）。通过这种方式，您可以利用计算机缓存，同时在列表头部进行摊销常数时间插入和删除，并且在列表中间进行摊销常数时间插入和删除，当您具有插入必须完成的元素之后的索引或要删除的元素的索引时（不需要移位/取消移位）。这方面的一个很好的参考是[CLRS 10.3]（https://books.google.it/books?id=NLngYyWFl_YC&lpg=PA209&pg=PA209#v=onepage&f=false）。 - Domenico De Felice

Answer 5

• 列表的优点在于，如果您需要在中间插入项目而不想开始调整数组并移动元素，则可以使用列表。
• 您说得对，通常情况下并非如此。我遇到过一些非常特定的情况，但并不是太多。

- Uri

---

当您在中间执行反转操作时，实际上是发生了数组的移位和调整大小。如果没有达到摊销界限，您只需要进行移位而无需调整大小。 - securecurve

Answer 6

这完全取决于您在迭代时执行的操作类型，所有数据结构在时间和内存之间存在权衡，在根据我们的需求选择正确的数据结构。因此，在某些情况下，LinkedList比数组更快，反之亦然。考虑数据结构上的三个基本操作。

搜索： 由于数组是基于索引的数据结构，搜索array.get（index）将花费O（1）的时间，而LinkedList不是索引DS，因此您需要遍历到索引处，其中index <= n，n是LinkedList的大小，因此当随机访问元素时，数组比LinkedList更快。

那么这背后的美在哪里？ 由于数组是连续的内存块，大块的数组将在第一次访问时加载到缓存中，这使得访问数组的其余元素相对较快，就像我们访问数组元素一样，引用局部性也会增加，从而减少了缓存未命中，缓存局部性是指操作在缓存中，因此与内存中相比执行速度更快，基本上在数组中，我们最大化了顺序元素访问在缓存中的机会。虽然链表不一定在连续的内存块中，但不能保证按顺序出现在列表中的项目实际上是排列在彼此附近的内存中，这意味着更少的缓存命中，例如需要为每次访问链表元素从内存中读取，这增加了访问它们所需的时间和降低了性能，因此如果我们执行更多的随机访问操作（即搜索），则数组将像下面解释的那样快。

插入： 在LinkedList中，这很容易且快速，因为在LinkedList中插入是O（1）操作（在Java中），而相比之下，在数组中，考虑到数组已满，如果数组已满，则需要将内容复制到新数组中，这使得将元素插入ArrayList的最坏情况为O（n），而ArrayList还需要更新其索引，如果您除了在数组末尾之外的任何地方插入某些内容，则需要调整索引。对于链表，我们不需要调整大小，只需要更新指针。

删除： 它的工作方式类似于插入，并且在LinkedList中比数组更好。

- Harleen

---

在列表中插入元素的最坏情况时间复杂度也是O(n)... - xyf

数组没有O(1)的搜索。访问和搜索是不同的。 - undefined

Answer 7

实际上，内存局部性在实际处理中具有巨大的性能影响。

"大数据"处理中磁盘流式处理的增加与随机访问相比表明，围绕此结构化应用程序可以在更大的规模上显着提高性能。

如果有任何一种方法可以按顺序访问数组，那么这是最好的性能。如果性能很重要，设计时应考虑这个目标。

- user3150186

Answer 8

这些是Collection最常用的实现方式。

ArrayList:

• 一般情况下在末尾插入/删除操作的时间复杂度为O(1)，最坏情况为O(n)。

• 在中间插入/删除操作的时间复杂度为O(n)。

• 任意位置检索的时间复杂度为O(1)。

LinkedList:

• 在任意位置插入/删除（如果你有元素的引用）操作的时间复杂度为O(1)。

• 在中间检索的时间复杂度为O(n)。

• 检索第一个或最后一个元素的时间复杂度为O(1)。

Vector：不要使用它。它是类似于ArrayList的旧实现，但所有方法都是同步的。在多线程环境中，这不是正确的共享列表的方法。

HashMap

按键插入/删除/检索的时间复杂度为O(1)。

TreeSet

按顺序插入/删除/包含的时间复杂度为O(log N)。

HashSet

插入/删除/包含/大小的时间复杂度为O(1)。

- Praveen Kumar Verma

Answer 9

我认为主要区别在于您是否经常需要插入或删除列表顶部的内容。

对于数组，如果从列表顶部删除某些内容，则复杂度为o（n），因为所有数组元素的索引都必须移动。

对于链表，它是o（1），因为您只需要创建节点，重新分配头并将引用分配给下一个作为先前的头。

当经常在列表末尾插入或删除时，数组更可取，因为复杂度将为o（1），不需要重新索引，但对于链表，它将为o（n），因为您需要从头到最后一个节点。

我认为在链表和数组中搜索都将是o（log n），因为您可能会使用二进制搜索。

- Curious_goat

Answer 10

数组是目前最广泛使用的数据结构。然而，在数组笨重或昂贵的情况下，链表以其独特的方式证明了自己的用处。

在大小可能变化的情况下，链表可用于实现堆栈和队列。链表中的每个节点都可以被推入或弹出，而不会干扰大多数节点。对于在中间插入/删除节点也是如此。然而，在数组中，所有元素都必须进行移位，这在执行时间方面是一项昂贵的工作。

二叉树和二叉搜索树、哈希表和字典树是一些数据结构，其中至少在C语言中，需要链表作为构建它们的基本组成部分。

然而，在期望能够通过索引调用任意元素的情况下，应避免使用链表。

- photonic