为什么有人要在数组上使用链表？
毫无疑问，对链表进行编码比使用数组需要更多的工作，而且人们可能想知道什么是额外努力的合理性。
我认为在链表中插入新元素是微不足道的，但它是数组中的一项主要工作。使用链表存储一组数据与将其存储在数组中相比，还有其他优势吗？
这个问题不是这个问题的重复，因为另一个问题是专门询问一个特定的 Java 类，而这个问题是关于一般数据结构的。
Onorio Catenacci
问问题
240323 次
34 回答
188
另一个很好的理由是链表非常适合高效的多线程实现。这样做的原因是更改往往是本地的 - 仅影响在数据结构的本地部分插入和删除的一两个指针。因此，您可以让许多线程在同一个链表上工作。更重要的是，可以使用 CAS 类型的操作创建无锁版本并完全避免重量级锁。
使用链表，迭代器也可以在修改发生时遍历链表。在修改不会发生冲突的乐观情况下，迭代器可以继续进行而不会发生争用。
对于数组，任何修改数组大小的更改都可能需要锁定数组的大部分，事实上，在整个数组没有全局锁定的情况下很少这样做，因此修改成为停止世界事务。
于 2008-10-03T13:59:08.167 回答
150
- 在链表中存储不同大小的数据更容易。数组假定每个元素的大小完全相同。
- 正如您所提到的，链表更容易有机地增长。数组的大小需要提前知道，或者在需要增长时重新创建。
- 洗牌一个链表只是改变什么指向什么的问题。洗牌数组更复杂和/或占用更多内存。
- 只要您的迭代都发生在“foreach”上下文中，您就不会在迭代中失去任何性能。
于 2008-10-03T13:40:05.723 回答
134
维基百科有很好的关于差异的部分。
与数组相比，链表有几个优点。元素可以无限期地插入到链表中，而数组最终会填满或需要调整大小，如果内存碎片化，甚至可能无法进行这种昂贵的操作。类似地，从其中删除了许多元素的数组可能会变得浪费地为空或需要变得更小。
另一方面，数组允许随机访问，而链表只允许顺序访问元素。实际上，单链表只能在一个方向上遍历。这使得链表不适用于通过索引快速查找元素很有用的应用程序，例如堆排序。由于引用和数据缓存的局部性，对数组的顺序访问也比在许多机器上的链表上更快。链表几乎没有从缓存中获得任何好处。
链表的另一个缺点是引用需要额外的存储空间，这通常使得它们对于诸如字符或布尔值之类的小数据项的列表是不切实际的。它也可能很慢，并且使用幼稚的分配器，浪费，为每个新元素单独分配内存，通常使用内存池解决问题。
于 2008-10-03T13:48:54.380 回答
60
我将添加另一个 - 列表可以充当纯粹的函数式数据结构。
例如，您可以让完全不同的列表共享相同的结尾部分
a = (1 2 3 4, ....)
b = (4 3 2 1 1 2 3 4 ...)
c = (3 4 ...)
IE：
b = 4 -> 3 -> 2 -> 1 -> a
c = a.next.next
无需将指向的数据复制a到bandc中。
这就是为什么它们在使用不可变变量的函数式语言中如此受欢迎的原因——prepend并且tail操作可以自由发生而无需复制原始数据——当您将数据视为不可变时，这是非常重要的特性。
于 2008-10-03T15:33:47.523 回答
29
除了插入到列表中间更容易 - 从链表中间删除也比数组更容易。
但坦率地说，我从未使用过链表。每当我需要快速插入和删除时，我也需要快速查找，所以我使用了 HashSet 或 Dictionary。
于 2008-10-03T13:39:11.107 回答
28
合并两个链表（尤其是两个双向链表）比合并两个数组要快得多（假设合并是破坏性的）。前者需要 O(1)，后者需要 O(n)。
编辑：为了澄清，我的意思是无序意义上的“合并”，而不是合并排序。也许“连接”会是一个更好的词。
于 2008-10-03T13:45:44.230 回答
18
一个广为人知的反对 ArrayList 和反对 LinkedList 的论点是LinkedList 在调试时不舒服。维护开发人员花在理解程序上的时间，例如发现错误，增加了，恕我直言，有时不能证明企业应用程序中性能改进的纳秒或内存消耗的字节数是合理的。有时（嗯，当然这取决于应用程序的类型），最好浪费几个字节，但有一个更易于维护或更容易理解的应用程序。
例如，在 Java 环境中并使用 Eclipse 调试器，调试 ArrayList 将显示一个非常容易理解的结构：
arrayList ArrayList<String>
elementData Object[]
[0] Object "Foo"
[1] Object "Foo"
[2] Object "Foo"
[3] Object "Foo"
[4] Object "Foo"
...
另一方面，查看 LinkedList 的内容并查找特定对象变成了点击展开树的噩梦，更不用说过滤掉 LinkedList 内部所需的认知开销了：
linkedList LinkedList<String>
header LinkedList$Entry<E>
element E
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
element E "Foo"
next LinkedList$Entry<E>
previous LinkedList$Entry<E>
...
previous LinkedList$Entry<E>
previous LinkedList$Entry<E>
previous LinkedList$Entry<E>
于 2009-11-01T06:17:32.690 回答
17
首先，在 C++ 中，链表不应该比数组更麻烦。您可以将std::list或boost 指针列表用于链表。链表与数组的关键问题是指针和可怕的随机访问所需的额外空间。如果你应该使用链表
- 您不需要随机访问数据
- 您将添加/删除元素，尤其是在列表中间
于 2008-10-03T13:51:34.077 回答
15
对我来说是这样的，
使用权
- 链表只允许顺序访问元素。因此算法复杂度为 O(n)
- 数组允许随机访问其元素，因此复杂度为 O(1)
贮存
- 链接列表需要额外的存储空间来存储引用。这使得它们对于诸如字符或布尔值之类的小数据项列表是不切实际的。
- 数组不需要额外的存储来指向下一个数据项。每个元素都可以通过索引访问。
尺寸
- 链表的大小本质上是动态的。
- 数组的大小仅限于声明。
插入/删除
- 可以在链表中无限地 插入和删除元素。
- 在数组中插入/删除值非常昂贵。它需要重新分配内存。
于 2010-10-30T10:57:19.910 回答
12
两件事情：
毫无疑问，对链表进行编码比使用数组需要更多的工作，他想知道如何证明额外的努力是合理的。
使用 C++ 时切勿编写链表。只需使用 STL。实现的难度绝不应该成为选择一种数据结构而不是另一种的理由，因为大多数数据结构已经实现了。
至于数组和链表之间的实际区别，对我来说最重要的是您计划如何使用该结构。我将使用术语向量，因为这是 C++ 中可调整大小数组的术语。
对链表进行索引很慢，因为您必须遍历列表才能找到给定的索引，而向量在内存中是连续的，您可以使用指针数学到达那里。
附加到链表的末尾或开头很容易，因为您只需更新一个链接，在向量中您可能需要调整大小并复制内容。
从列表中删除项目很容易，因为您只需断开一对链接，然后将它们重新连接在一起。从向量中删除一个项目可能更快或更慢，这取决于您是否关心订单。将最后一个项目交换到您要删除的项目之上会更快，而在它向下移动之后的所有内容会更慢但保留顺序。
于 2008-10-03T13:53:43.403 回答
10
Eric Lippert 最近发表了一篇关于应该保守使用数组的原因之一的帖子。
于 2008-10-03T13:40:22.540 回答
8
快速插入和删除确实是链表的最佳论据。如果您的结构动态增长并且不需要对任何元素进行恒定时间访问（例如动态堆栈和队列），那么链表是一个不错的选择。
于 2008-10-03T13:43:13.953 回答
7
这是一个快速的：删除项目更快。
于 2008-10-03T13:39:24.057 回答
7
除了从列表中间添加和删除之外，我更喜欢链表，因为它们可以动态增长和收缩。
于 2008-10-03T13:41:56.313 回答
7
当集合不断增长和缩小时，链表特别有用。例如，很难想象尝试使用数组来实现一个队列（添加到末尾，从前面删除）——您将把所有的时间都花在向下移动上。另一方面，它对于链表来说是微不足道的。
于 2008-10-03T13:46:02.560 回答
7
再也没有人编写自己的链表了。那会很愚蠢。使用链表需要更多代码的前提是错误的。
这些天来，建立一个链接列表只是学生的一个练习，以便他们能够理解这个概念。相反，每个人都使用预先构建的列表。在 C++ 中，根据我们问题中的描述，这可能意味着一个 stl 向量 ( #include <vector>)。
因此，选择链表与数组完全是权衡每个结构的不同特征与您的应用程序的需求相关。克服额外的编程负担对决策的影响应该为零。
于 2008-10-03T13:51:01.847 回答
7
数组与链表：
- 数组内存分配有时会因为内存碎片而失败。
- 数组中的缓存更好，因为所有元素都分配了连续的内存空间。
- 编码比数组更复杂。
- 与数组不同，链表没有大小限制
- 链表中的插入/删除速度更快，数组中的访问速度更快。
- 从多线程的角度来看，链表更好。
于 2012-12-26T22:40:44.000 回答
6
这实际上是一个效率问题，在链表中插入、删除或移动（不是简单地交换）元素的开销是最小的，即操作本身是 O(1)，而数组是 O(n)。如果您对数据列表进行大量操作，这可能会产生重大影响。您根据您将如何操作它们来选择您的数据类型，并为您使用的算法选择最有效的。
于 2008-10-03T13:51:18.947 回答
6
数组在项目的确切数量已知的情况下是有意义的，在按索引搜索的情况下是有意义的。例如，如果我想在给定时刻存储视频输出的确切状态而不进行压缩，我可能会使用大小为 [1024][768] 的数组。这将为我提供我所需要的确切信息，并且获取给定像素的值的列表会慢得多。在数组没有意义的地方，通常有比列表更好的数据类型来有效地处理数据。
于 2008-10-03T14:08:35.387 回答
3
由于数组本质上是静态的，因此内存分配等所有操作仅在编译时发生。所以处理器必须在其运行时付出更少的努力。
于 2009-08-30T13:57:42.960 回答
3
假设您有一个有序集，您还想通过添加和删除元素来修改它。此外，您需要能够保留对元素的引用，以便以后可以获取上一个或下一个元素。例如，待办事项列表或书中的一组段落。
首先我们应该注意，如果您想保留对集合本身之外的对象的引用，您最终可能会将指针存储在数组中，而不是存储对象本身。否则，您将无法插入数组 - 如果对象嵌入到数组中，它们将在插入期间移动，并且指向它们的任何指针都将变为无效。数组索引也是如此。
正如您自己所指出的，您的第一个问题是插入 - 链表允许在 O(1) 中插入，但数组通常需要 O(n)。这个问题可以部分克服——可以创建一个数据结构，提供类似数组的按序访问接口，其中读取和写入在最坏的情况下都是对数的。
您的第二个也是更严重的问题是，给定一个元素找到下一个元素是 O(n)。如果集合没有被修改，你可以保留元素的索引作为引用而不是指针，从而使 find-next 成为 O(1) 操作，但你所拥有的只是一个指向对象本身的指针，没有办法确定其在数组中的当前索引，而不是通过扫描整个“数组”。这对于数组来说是一个无法克服的问题——即使你可以优化插入，也无法优化 find-next 类型的操作。
于 2010-07-26T04:40:43.243 回答
3
在数组中，您有权在 O(1) 时间内访问任何元素。因此它适用于二进制搜索快速排序等操作。另一方面，链表适用于插入删除，因为它在 O(1) 时间内。两者都有优点和缺点，并且更喜欢一个而不是另一个归结为您想要实现的内容。
-- 更大的问题是我们能否将两者混合使用。类似于 python 和 perl 实现为列表的东西。
于 2010-08-29T11:42:10.373 回答
3
链表
当涉及到插入时，它更可取！基本上它的作用是处理指针
1 -> 3 -> 4
插入 (2)
1............3......4
......2
最后
1 -> 2 -> 3 -> 4
从 2 点到 3 的一个箭头和从 1 点到 2 的箭头
简单的！
但是从数组
| 1 | 3 | 4 |
插入 (2) | 1 | 3 | | 4 | | 1 | | 3 | 4 | | 1 | 2 | 3 | 4 |
好吧，任何人都可以想象其中的区别！仅针对 4 个索引，我们执行 3 个步骤
如果数组长度是一百万呢？阵列有效吗？答案是不！:)
删除也是一样！在链表中，我们可以简单地使用指针并在对象类中使元素和下一个无效！但是对于数组，我们需要执行 shiftLeft()
希望有帮助！:)
于 2013-08-30T19:31:15.743 回答
3
Linked List 比数组更需要维护，它还需要额外的内存存储所有这些点都是一致的。但是有一些事情是数组无法做到的。在许多情况下，假设您想要一个长度为 10^9 的数组，您无法获得它，因为必须在那里获得一个连续的内存位置。链接列表可能是这里的救星。
假设你想用数据存储多个东西，那么它们可以很容易地在链表中扩展。
STL 容器通常在幕后实现链表。
于 2015-07-29T06:01:31.740 回答
3
1-链表是一种动态数据结构，因此它可以通过分配和释放内存在运行时增长和缩小。所以不需要给出链表的初始大小。节点的插入和删除真的很容易。
2-链表的大小可以在运行时增加或减少，因此没有内存浪费。在数组的情况下，有很多内存浪费，比如如果我们声明一个大小为 10 的数组并在其中只存储 6 个元素，则浪费了 4 个元素的空间。链表中没有这样的问题，因为只有在需要时才分配内存。
3-使用链表可以轻松实现堆栈和队列等数据结构。
于 2019-10-12T09:06:05.840 回答
2
于 2008-10-03T14:09:26.163 回答
1
我也认为链接列表比数组更好。因为我们在链表中遍历而不是在数组中遍历
于 2008-10-27T06:59:00.290 回答
1
根据您的语言，可以考虑以下一些缺点和优点：
C 编程语言：使用链表（通常通过结构指针）时，必须特别注意确保您没有泄漏内存。如前所述，链表很容易洗牌，因为所做的只是改变指针，但我们会记住释放所有东西吗？
Java：Java 具有自动垃圾收集功能，因此内存泄漏不会成为问题，但对高级程序员隐藏的是链表的实现细节。诸如从列表中间删除一个节点之类的方法比该语言的某些用户所期望的要复杂得多。
于 2012-06-20T17:45:30.193 回答
1
为什么在数组上使用链表？正如一些人已经说过的，插入和删除的速度更快。
但也许我们不必忍受两者的限制，同时获得两者的最佳……嗯？
对于数组删除，您可以使用“已删除”字节来表示已删除行的事实，因此不再需要重新组织数组。为了减轻插入或快速更改数据的负担，请为此使用链表。然后在引用它们时，让你的逻辑先搜索一个，然后再搜索另一个。因此，结合使用它们可以为您带来两全其美的效果。
如果你有一个非常大的数组，你可以将它与另一个小得多的数组或链表结合起来，其中较小的一个包含 20、50、100 个最近使用的项目。如果需要的不在较短的链表或数组中，则转到大数组。如果在那里找到，您可以将其添加到较小的链表/数组中，假设“最近使用的东西最有可能被重复使用”（是的，可能会从列表中碰撞最近最少使用的项目）。这在许多情况下都是正确的，并且解决了我必须在 .ASP 安全权限检查模块中解决的问题，轻松、优雅和令人印象深刻的速度。
于 2015-07-09T21:01:19.517 回答
1
虽然你们中的许多人都谈到了链表与数组的主要 adv./dis，但大多数比较是一个比另一个更好/更差的比较。例如。您可以在数组中进行随机访问，但在链表等中则不可能。但是，这是假设链接列表和数组将应用于类似的应用程序中。然而，正确的答案应该是在特定的应用程序部署中链接列表如何优于数组，反之亦然。假设你想实现一个字典应用程序，你会用什么？数组：嗯，它可以通过二进制搜索和其他搜索算法轻松检索......但让我们想想链接列表如何更好......假设你想在字典中搜索“Blob”。有一个 A->B->C->D----> 的链接列表是否有意义
A -> B -> C -> ...Z
| | |
| | [Cat, Cave]
| [Banana, Blob]
[Adam, Apple]
现在是上述方法更好还是 [Adam,Apple,Banana,Blob,Cat,Cave] 的平面数组？甚至可以使用 array 吗？所以链接列表的一个主要优点是你可以让一个元素不仅指向下一个元素，还可以指向其他链接列表/数组/堆/或任何其他内存位置。数组是一个平坦的连续内存，它被分割成它要存储的元素的块大小。另一方面，链接列表是一块非连续的内存单元（可以是任何大小并且可以存储任何东西）并指向每个其他你想要的方式。同样，假设您正在制作 USB 驱动器。现在您希望将文件保存为任何数组还是链接列表？我想你明白我的意思了:)
于 2016-09-28T05:35:22.550 回答
1
为什么有人要在数组上使用链表？
这只是一个原因 - 如果您需要链表数据结构并且您使用的编程语言不支持指针。
于 2017-12-07T13:44:50.037 回答
1
除了插入和删除方便之外，链表的内存表示方式与数组不同。链表中的元素数量没有限制，而在数组中，您必须指定元素的总数。检查这篇文章。
于 2019-05-12T11:53:20.780 回答
0
使用链接列表的人必须阅读。人们会再次爱上阵列。它讨论了乱序执行、硬件预取、内存延迟等。
http://www.futurechips.org/thoughts-for-researchers/quick-post-linked-lists.html
于 2011-09-05T17:16:47.727 回答
0
数组和链表的区别在于数组是基于索引的数据结构，每个元素都与索引相关联，而链表是使用引用的数据结构，每个节点都引用另一个节点。在数组中大小是固定的，而在链接列表中大小是不固定的。
于 2019-03-14T12:11:17.110 回答