何时使用链表而不是列表？

Question

4

我正在使用Python学习数据结构和算法。我已经学到，链表的优点是它没有最大节点数的限制，不像其他语言中的数组。

1. 因为Python会为我们自动调整列表大小，所以这个优点已经被抽象化了。 2. 因此，我一直认为链表唯一的优势就是在链表前面或后面添加一个节点是O（1），而向列表添加元素可能会因为Python需要调整数组大小并复制每个元素而变成O（n）。

但是，我刚学到摊销时间复杂度是今天的一件事情，并且向列表附加元素的摊销时间复杂度为O(1)。因此，向列表添加元素实际上比添加节点到链表更快，因为添加节点到链表除链表前/后以外的任何位置都需要O(n)的时间复杂度。

那么，在使用数组/列表方面，使用链表有什么意义呢？

- rank1psysuck

2

你并不总是想要将元素添加到列表的末尾。对于需要在任意位置插入或移动元素的任务（例如从末尾取出一个元素并将其移到开头），链表的时间复杂度为O(1)，而数组的时间复杂度为O(n)。不同的数据结构在不同情况下都有其优缺点。请注意，这与Python无关！ - Samwise

5

一般而言，如今很少使用链表。现代处理器使用缓存和预读取技术，因此内存局部性非常重要。缓存未命中和页面错误的代价极高。实际上，链表由于其不连续的访问模式，在实践中表现不佳，即使在理论上它们的O(1)操作应该比数组的O(n)更快。 - John Kugelman

链表确实有其使用场景，但与动态数组相比，这些场景要少得多。 - user2357112

作为一名实践者，在Python中你不会使用链表。理解链表的概念是为了在使用其他非Python语言编写代码时能够识别和使用它们。 - Charles Duffy

1

@CharlesDuffy 双端队列使用链表，你是说双端队列在实践中不被使用吗？ - Kelly Bundy

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ti7 · Accepted Answer

尽管可以构建一些例子来展示它们的用途（在一个人为制造的情况下，也许你正在使用的工业ASIC需要它们），但是特别是链表的微不足道的实现通常只是作为一个例子而存在，并且在现实中往往会制造出处理器缓存失效¹，导致性能比在纸上看起来要差几个数量级。

然而，它们是以下方面的一个极好的例子：

指针的清晰、完整和最小教学演示
一些更有用、更具有一般性的概念
- 中间数据插入而不移动大量相邻数据是可能的。
- 对于工作所涉及的数据结构的长度并不是必需知道的。
- 通常不必立即存储除活动和下一个数据以外的更多数据。

链表也可能在计算机科学之外有用，例如，在生物过程中他们可能表现得非常有效。

备注
1. 尚在寻找精确的例子，但我记得谷歌有一个很棒的演讲，介绍了为什么他们不在内部使用某些stdlib，以防止意外地使用链表和其他一些类型，原因是降低了性能/增加了错误的数量。