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

Question

许多编程语言提供内置数据结构,但已知某些数据结构(例如链表)非常易于实现,因此,语言通常不包括内置数据结构.某些语言(如C++)具有(如std::list双链接),以及Java(如LinkedList<T>双链接).

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

请注意,Python列表的基础数据结构实际上是一个数组,如"Python列表的基础数据结构是什么？"中所述..此外,双端队列中collections是一个双端队列,其应具有缺少的功能,因为它通常不会支持索引或插入在中间(然而,索引特征已经自3.5具有添加index和insert,但不存在在Python 2).

似乎提供内置数据LinkedList结构是多余的,不必要的.为什么其他一些编程语言库(如C++和Java库)包含数据LinkedList结构,即使它们易于实现？如果是这样,在这些语言中实施您自己的链表有什么风险？

Answer 1

我搜索了Guido的Python历史博客,因为我确信他已经写过这个,但显然这不是他这样做的地方.因此,这是基于推理(又名有根据的猜测)和记忆(可能有缺陷)的组合.

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

是的,我们这样做.简短的版本是:二十多年来没有人要求它.几年来内置或标准库中添加的内容几乎都是(一种变体)在PyPI或ActiveState配方上被证明有用和流行的东西.这就是OrderedDict和defaultdict从,例如来了,enum和dataclass(基于attrs).有用于分类字典/套,OrderedSet,树木和尝试,等一些其他类型的容器,各种排列流行的库,都SortedContainers和blist已经被提出,但遭到拒绝,列入STDLIB.

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

因此,这使问题又回到了一步:为什么没有流行的链表库？

首先,"链表"实际上不是一种类型,而是整个类型的系列 - 单一与双链接,节点列表与句柄列表,尾部共享与否,懒惰(可能是通过@property样式触发器)或严格...以及像圆形列表的变化.当然,这些中的每一个都远远不如整个家庭.并且你不能在它们的接口或实现之间共享那么多 - 用于处理Lisp样式cons列表的接口对于类似C++的东西毫无意义std::list.

其次,所有不同的变化都很容易构建.OrderedDict使其成为语言的原因是人们能够证明实现这一目标非常棘手.集合很容易正确,但如果不借用幕后的实现细节,就不可能进行空间优化.链接列表很容易正确和优化.如果你想要一个,任何一个品种,你在几分钟内建立一个,你就完成了.(事实上​​,OrderedDict在引擎盖下使用一个...)

同时,自Python 2.3以来,特别是3.0以来,迭代器协议已成为一切的核心范例.其他语言借用Python的生成器是有原因的 - 但在大多数语言中,它们并没有提供相同的好处,因为整个语言并非围绕它们构建.能够对任何集合进行前向迭代 - 包括甚至不存在的"虚拟"集合 - 已经为您提供了懒惰的尾部共享缺点列表的大部分优点,而无需一个.另一方面,它缺少的主要是方便的恒定时间(变异)拼接 - 但是缺少的东西实际上很难适应迭代器范例.(看看itertools你是如何做到的 - 它只是tee而且chain,毕竟 - 这样做有多笨拙.)

(当然,对于更复杂的迭代协议也有优势,比如C++使用的协议,或者更好的是Swift.通过双向和可变与不可变迭代,双链表可能更有用.但是在那里权力和简单之间的权衡,很久以前Python就做出了选择.)

而且,最后,但绝对不是最不重要的,链表,特别是cons-style尾部共享链表,是一种固有的递归数据结构.Python的哲学是只有当你有固有的递归问题时才使用递归.而Guido认为这些很少,这就是Python不做的原因,例如尾部递归消除.他不想map和reduce他的语言,但是一旦他想出了如何做这些迭代,而不是递归,他愿意让他们留下.存储线性数据并不是一个固有的递归问题.树？当然,它们几乎必须是递归的.但是列表？没有.