为什么像C++和Java这样的语言会有内置的LinkedList数据结构？

Question

许多编程语言都提供内置数据结构，尽管某些数据结构（例如链表）易于实现，因此语言通常不包括它作为内置数据结构。一些语言，例如C++（作为std::list，双向链接）和Java（作为LinkedList<T>，双向链接）则提供了这样的数据结构。

例如，Python已经在其库中内置了几种数据结构，包括列表、元组、集合、字典（甚至不需要导入），以及来自collections库的数据结构。它没有内置LinkedList数据结构，因为在Python中，实现自己的LinkedList已经很容易了。

请注意，Python列表的底层数据结构实际上是一个数组，如"Python列表的底层数据结构是什么？"中所回答的。此外，collections中的deque是一个双端队列，由于通常不支持索引或在中间插入而可能缺少某些功能（但自3.5以来已添加了索引功能和insert，但在Python 2中不存在）。

似乎提供内置的LinkedList数据结构是多余和不必要的。为什么一些其他编程语言库（如C++和Java库）包括LinkedList数据结构，即使它们很容易实现？如果这样做，使用这些语言实现自己的链表有哪些风险？

- anon

---

我记得Guido在他的Python History博客中提到过这个问题，但我找不到了。如果我没记错的话，他的观点是：链表有很多不同的选项（单向或双向？节点作为列表还是作为句柄？可变或不可变？共享尾部？），它们在Python中都很容易构建，在C语言中实现它们并没有真正的速度或空间优势（不像数组或哈希表），而且没有一个选项比其他选项更常用，因此无需内置。 - abarnert

链表通常是一个可怕的想法。它们的主要优点在于它们很容易实现。特别是，大多数真实世界中的链表都是特定目的的侵入式链表，而不是类似容器的链表。 - o11c

@abarnert，你能找到这个吗？这将非常有用，可以提供一个正确的答案。 - Cosmo

@abarnert 我一直在考虑写一个推测性答案，结合您的评论和来自各种语言的链表API文档中的引用，大致是“几乎总是最好使用我们的连续可调整大小的数组或我们的双端队列而不是我们的链表。一般来说，基于数组的容器更快，更节省内存，并更好地利用CPU缓存。”不过我还是有点新手，所以不确定这样的推测在实际答案中是否被禁止。 - Cosmo

@Cosmo 标准答案是，您几乎总是希望使用宽树或长绳，以获得两者的最佳结合...除非实际上，您不需要将规模扩展到30亿个元素，并且仍然在中间拼接，因此您只需要一个数组。Raymond Hettinger在关于“blist”pep的评论可能与此相关。 - abarnert

Answer 1

我搜索了Guido的Python History博客，因为我确定他写过这个问题，但显然他没有。因此，这是基于推理（又称有根据的猜测）和记忆（可能不准确）的结合。

让我们从最后开始：即使我们不知道Guido为什么没有在Python 0.x中添加链表，我们是否至少知道为什么核心开发人员自那以后没有添加它们，尽管他们已经添加了一堆其他类型，从OrderedDict到set？

是的，我们知道。简短版本是：20多年来没有人提出要求。多年来添加到内置或标准库中的几乎所有内容都是已被证明有用且受欢迎的PyPI或ActiveState recipes上的某种变体。例如，OrderedDict和defaultdict就是这样产生的，而enum和dataclass则是基于attrs。还有一些其他容器类型的流行库，如各种排序字典/集合的排列、OrderedSet、树和tries等，而SortedContainers和blist都曾被提议加入标准库，但被拒绝了。

但是，没有流行的链表库，这就是为什么它们永远不会被添加的原因。

那么，问题又回到了最初：为什么没有流行的链表库？

首先，“链表”并不是一个真正的类型，而是一个完整的类型族——单向链表 vs. 双向链表、节点作为列表 vs. 句柄作为列表、是否共享尾部、通过@property风格触发器实现延迟或严格等等，以及诸如循环列表之类的变体。当然，每个变体都比整个类型族有用得多。而且你不能在它们之间共享太多接口或实现——处理类似Lisp-style cons列表的接口对于像C++ std::list这样的东西根本没有意义。

其次，所有不同的变体都非常容易构建。OrderedDict能够进入语言的原因是人们能够证明它实际上很难正确实现。集合易于正确实现，但如果没有从字典中借用后台实现细节，则不可能进行空间优化。链表易于正确实现和优化。如果您需要其中任何一种，只需几分钟就可以构建一个，并完成任务。（事实上，OrderedDict在幕后使用了其中之一……）

与此同时，自Python 2.3以来，特别是自3.0以来，迭代器协议已成为一切的中心范式。其他语言借鉴Python的生成器有其原因，但在这些大多数语言中，它们并没有提供相同的好处，因为整个语言都不是围绕它们构建的。能够向前迭代任何集合，包括甚至不存在的“虚拟”集合，已经让你获得了大部分惰性尾共享cons列表的优势，而无需一个。另一方面，它主要缺少方便的常数时间（变异）拼接，但这一个缺失的东西实际上很难适应迭代器范例。（请参见itertools，了解如何做到这一点-这只是tee和chain，以及如何做起来感觉笨拙。）

（当然，更复杂的迭代协议也有优势，比如C++使用的协议，或者更好的Swift。通过双向和可变与不可变迭代，双向链表可能会更加有用。但在权力和简单之间存在权衡，Python早就做出了选择。）

而且，最后但绝不是最不重要的，链表，特别是cons-style tail-sharing链表，是一种固有的递归数据结构。Python哲学是仅在具有固有递归问题时使用递归。Guido认为这类问题很少，这就是为什么Python不执行尾递归消除等操作的原因。他不想让map和reduce成为他的语言的一部分，但一旦他找到了迭代地解决它们的方法，他愿意让它们保留。存储线性数据不是一个固有的递归问题。树？当然，它们几乎必须是递归的。但是列表呢？不是。

- abarnert