首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >为什么像C++和Java这样的语言有一个内置的LinkedList数据结构?

问为什么像C++和Java这样的语言有一个内置的LinkedList数据结构?
EN

Stack Overflow用户
提问于 2018-05-12 21:15:31
回答 1查看 2.3K关注 0票数 4

许多编程语言都提供内置的数据结构,尽管一些数据结构(如链接列表)被认为很容易实现,因此,语言通常不将其作为内置的数据结构。有些语言,如C++有 (作为std::list,双链接),以及Java (作为LinkedList<T>,双链接)。

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

请注意,基础数据结构-- Python列表--实际上是一个数组,这在“Python列表的底层数据结构是什么?”中得到了回答。另外,collections中的deque是一个双端队列,它应该有缺少的特性,因为它通常不支持索引或中间插入(但是,索引功能从3.5开始就用index和insert添加了,但是在Python2中不存在)。

提供内置的LinkedList数据结构似乎是多余和不必要的。为什么其他一些编程语言库(如C++和LinkedList库)包括LinkedList数据结构,即使它们可以很容易实现?如果是的话,用这些语言实现自己的链接列表的风险有多大?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2018-05-13 06:23:13

我搜索了Guido的Python历史博客,因为我确信他写过这篇文章,但显然他不是这么做的。因此,这是基于推理(也就是受过教育的猜测)和记忆(可能有缺陷)的结合。

让我们从结尾开始:不知道为什么Guido没有在Python0.x中添加链接列表,我们至少知道为什么核心开发人员从那时起就没有添加链接列表了,尽管它们添加了从OrderedDict到set的其他类型

是的,我们有。简略的说法是:二十多年来,没有人要求这样做。这些年来添加到内置程序或标准库中的内容几乎都是一些在PyPI或ActiveState配方上被证明是有用和流行的东西。例如,这就是OrderedDict和defaultdict以及enum和dataclass (基于attrs)的来源。还有一些其他容器类型的流行库--排序dict/set、OrderedSet、树和尝试等的各种排列,SortedContainers和blist都被提议,但被拒绝,以便包含在stdlib中。

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

因此,这让问题又回到了一个步骤:为什么没有流行的链接列表库?

首先,“链接列表”并不是真正的一种类型,而是一个完整的类型系列--单类型与双链接类型、节点即列表类型与句柄类型列表、尾共享类型和不类型类型、延迟类型(可能通过@property-style触发器)或严格的…类型。以及类似循环列表的变化。当然,它们中的每一个都比整个家庭有用得多。而且您不能在接口或它们的实现之间共享所有的东西--处理Lisp样式的cons列表的接口对于C++ std::list之类的东西根本没有意义。

其次,所有不同的变体都非常容易构建。OrderedDict之所以把它写成这种语言,是因为人们能够证明它实际上是很难纠正的。集很容易得到正确,但不可能空间优化而不借用幕后实现细节的分块。链接列表很容易得到正确和优化。如果你想要一个,任何一个品种,你可以在几分钟内建立一个,你就完成了。(事实上,OrderedDict使用的是引擎盖下的…)

同时,自从Python2.3,特别是3.0以来,迭代器协议已经成为所有事物的中心范例。其他语言借用Python的生成器也是有原因的,但在大多数这些语言中,它们并没有提供相同的好处,因为整个语言并不是以它们为基础的。能够转发--迭代任何集合--包括一个根本不存在的“虚拟”集合,已经给您提供了懒散的共享尾部的反列表的大部分优点。另一方面,它所缺少的主要东西是方便的恒定时间(变异)剪接,但这一缺失的东西实际上很难适应迭代器范例。(关于如何做到这一点,请参见itertools --毕竟,这只是tee和chain --以及这样做有多么笨拙。)

(当然,更复杂的迭代协议也有好处,比如C++使用的迭代协议,或者更好的Swift协议。对于双向和可变的和不变的迭代,双链接列表可能会更有用。但是在强大和简单之间有一种权衡,Python很久以前就做出了选择。)

最后,但绝对不是最不重要的是,链接列表,特别是反式尾共享链接列表,是一种固有的递归数据结构。Python的理念是,只有当您有固有的递归问题时才使用递归。Guido认为这种情况非常少,这就是Python不做尾递归消除的原因。他不希望map和reduce出现在他的语言中,但是一旦他想出了如何迭代而不是递归的方法,他就愿意让他们留下来。而存储线性数据并不是一个固有的递归问题。树?当然,它们必须是递归的。但是名单呢?不是的。

票数 11
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/50310731

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档