java - 为什么某些语言(例如C++和Java)具有内置的“链表”数据结构？

Question

Closed. This question is opinion-based。它当前不接受答案。












想要改善这个问题吗？更新问题，以便 editing this post用事实和引用来回答。

2年前关闭。



Improve this question




尽管有些数据结构(例如 链表)非常易于实现，但许多编程语言都提供了内置数据结构，因此，语言通常不将其包括在内。
某些语言，例如 C++ has(双向链接)， as well as Java(双向链接)。

例如，Python已经在其库中内置了几种数据结构，包括列表，元组，集合，字典(甚至不需要导入)，以及 std::list库中的数据结构。它没有内置的 LinkedList<T>数据结构，因为在Python中已经很容易实现您自己的LinkedList。

请注意，Python列表的底层数据结构实际上是 "What is the underlying data structure for Python lists?"中回答的数组。另外， collections中的双端队列是双端队列，应该缺少一些功能，因为它通常不支持索引或在中间插入(但是，自3.5起， LinkedList和 collections已添加了索引功能，但不是出现在Python 2中)。

似乎提供内置的 index数据结构是多余且不必要的。为什么某些其他编程语言库(例如C++和Java库)即使易于实现也包含 insert数据结构？如果是这样，用这些语言实现自己的链表有什么风险？

最佳答案

我搜索了Guido的Python History博客，因为我确定他已经写过有关此的内容，但是显然那不是他这样做的地方。因此，这是基于推理(又称有根据的猜测)和内存(可能是错误的)的组合。

让我们从头开始:在不知道Guido为什么不在Python 0.x中添加链接列表的情况下，我们是否至少知道为什么核心开发者从那时起就没有添加链接列表，即使他们添加了许多其他类型从OrderedDict到set？

是的，我们愿意。简短的版本是:在过去的二十多年中，没有人要求它。这些年来，几乎所有添加到内建函数或标准库中的东西(都是其变体)在PyPI或ActiveState recipes上被证明是有用且流行的。那里就是OrderedDict和defaultdict以及enum和dataclass(基于attrs)的来源。对于其他一些容器类型，也有流行的库-排序的dict/set，OrderedSet，tree和try等的各种排列，并且有人建议同时将SortedContainers和blist包含在stdlib中。

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

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

首先，“链接列表”实际上不是一种类型，而是一整套类型-单链与双链，节点列表与列表句柄，是否共享尾部，是否懒惰(大概是通过@property-样式触发器)或严格…以及类似循环列表的变体。当然，其中每一项的用处远不及整个家庭有用。而且，您在接口(interface)或实现之间不能共享太多的东西-用于处理Lisp样式的cons列表的接口(interface)对于C++ std::list之类的东西根本没有任何意义。

其次，所有不同的变体都是很容易构建的。 OrderedDict成为语言的原因是人们能够证明正确正确的做法非常棘手。集合很容易正确使用，但如果不从字典中借用幕后实现细节，就不可能进行空间优化。链接列表很容易正确和优化。如果您想要一个任何品种，您都可以在几分钟内建立一个品种，然后就完成了。 (实际上，OrderedDict在后台使用了一个…)

同时，自Python 2.3(尤其是3.0)以来，迭代器协议(protocol)已成为一切的主要范例。还有其他语言借用Python的生成器的原因-但是在大多数这些语言中，它们没有提供相同的好处，因为整个语言不是围绕它们构建的。能够转发迭代任何集合(包括一个甚至不存在的“虚拟”集合)的能力，已经为您提供了一个懒惰的共享尾部缺点列表的大部分优点，而无需其中一个。另一方面，它缺少的主要东西是方便的恒定时间(变异)拼接-但是实际上缺少一个缺失的东西很难放入迭代器范式中。 (有关详细信息，请参阅itertools-毕竟只是tee和chain-以及这样做的感觉多么笨拙。)

(当然，更复杂的迭代协议(protocol)也有优势，例如C++使用的协议(protocol)，或者甚至更好的Swift协议(protocol)。通过双向可变和不可变的迭代，双向链接列表可能会有用得多。但是，在功能和简单之间进行权衡，Python早就做出了选择。)

最后，但绝对重要的是，链表，尤其是cons样式的尾部共享链表，是一种固有的递归数据结构。 Python的哲学是仅在存在固有的递归问题时才使用递归。 Guido相信其中很少，这就是为什么Python不这样做的原因，例如尾递归消除。他不希望使用他的语言来使用map和reduce，但是一旦他想出了如何迭代而不是递归地执行它们，他便愿意保留它们。而且，存储线性数据并不是天生的递归问题。树木？当然，它们几乎必须是递归的。但是 list ？不。

关于java - 为什么某些语言(例如C++和Java)具有内置的“链表”数据结构？ ，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/50310731/

上一篇：c++ - 用于包括 guard 的名称？

下一篇：c++ - 检查一个文本文件中的单词是否在第二个文本文件中 (C++)

相关文章：

java - 为什么 G1 提供更好的暂停时间但吞吐量较低？

python - scikit-learn:如何使用管道组合 LabelEncoder 和 OneHotEncoder？

python - 为什么数组中的输入会覆盖每一行的值

C++ 从函数返回 double 或 int

c++ - 为什么我不能在 SQLite 中的 VIEW 上创建触发器？

c++ - 尝试获取命令行参数的核心转储。 (C++)

java - 用于开发 iPhone 推送通知服务的 Google App Engine 的 Java 替代品是什么？

java - 无法引用迭代器中以前使用过的元素(java)

java - 使用 Buffered Reader 读取输入的语句未执行

python - 是否可以设置 lint 自定义设置并忽略 pylance

Answer 1

我搜索了Guido的Python History博客，因为我确定他已经写过有关此的内容，但是显然那不是他这样做的地方。因此，这是基于推理(又称有根据的猜测)和内存(可能是错误的)的组合。

让我们从头开始:在不知道Guido为什么不在Python 0.x中添加链接列表的情况下，我们是否至少知道为什么核心开发者从那时起就没有添加链接列表，即使他们添加了许多其他类型从OrderedDict到set？

是的，我们愿意。简短的版本是:在过去的二十多年中，没有人要求它。这些年来，几乎所有添加到内建函数或标准库中的东西(都是其变体)在PyPI或ActiveState recipes上被证明是有用且流行的。那里就是OrderedDict和defaultdict以及enum和dataclass(基于attrs)的来源。对于其他一些容器类型，也有流行的库-排序的dict/set，OrderedSet，tree和try等的各种排列，并且有人建议同时将SortedContainers和blist包含在stdlib中。

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

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

首先，“链接列表”实际上不是一种类型，而是一整套类型-单链与双链，节点列表与列表句柄，是否共享尾部，是否懒惰(大概是通过@property-样式触发器)或严格…以及类似循环列表的变体。当然，其中每一项的用处远不及整个家庭有用。而且，您在接口(interface)或实现之间不能共享太多的东西-用于处理Lisp样式的cons列表的接口(interface)对于C++ std::list之类的东西根本没有任何意义。

其次，所有不同的变体都是很容易构建的。 OrderedDict成为语言的原因是人们能够证明正确正确的做法非常棘手。集合很容易正确使用，但如果不从字典中借用幕后实现细节，就不可能进行空间优化。链接列表很容易正确和优化。如果您想要一个任何品种，您都可以在几分钟内建立一个品种，然后就完成了。 (实际上，OrderedDict在后台使用了一个…)

同时，自Python 2.3(尤其是3.0)以来，迭代器协议(protocol)已成为一切的主要范例。还有其他语言借用Python的生成器的原因-但是在大多数这些语言中，它们没有提供相同的好处，因为整个语言不是围绕它们构建的。能够转发迭代任何集合(包括一个甚至不存在的“虚拟”集合)的能力，已经为您提供了一个懒惰的共享尾部缺点列表的大部分优点，而无需其中一个。另一方面，它缺少的主要东西是方便的恒定时间(变异)拼接-但是实际上缺少一个缺失的东西很难放入迭代器范式中。 (有关详细信息，请参阅itertools-毕竟只是tee和chain-以及这样做的感觉多么笨拙。)

(当然，更复杂的迭代协议(protocol)也有优势，例如C++使用的协议(protocol)，或者甚至更好的Swift协议(protocol)。通过双向可变和不可变的迭代，双向链接列表可能会有用得多。但是，在功能和简单之间进行权衡，Python早就做出了选择。)

最后，但绝对重要的是，链表，尤其是cons样式的尾部共享链表，是一种固有的递归数据结构。 Python的哲学是仅在存在固有的递归问题时才使用递归。 Guido相信其中很少，这就是为什么Python不这样做的原因，例如尾递归消除。他不希望使用他的语言来使用map和reduce，但是一旦他想出了如何迭代而不是递归地执行它们，他便愿意保留它们。而且，存储线性数据并不是天生的递归问题。树木？当然，它们几乎必须是递归的。但是 list ？不。