Python是否使用列表的链接列表？为什么插入慢？

Question

刚刚学习Python.阅读官方教程.我碰到了这个:

虽然列表末尾的追加和弹出很快,但是从列表的开头进行插入或弹出是很慢的(因为所有其他元素都必须移动一个).

我猜想像Python这样的成熟语言会有各种各样的优化,那么为什么Python [似乎]不会使用链接列表以便插入速度快？

Answer 1

Python在内存中使用线性列表布局,因此索引很快(O(1)).

Answer 2

正如Greg Hewgill已经指出的那样,python列表使用连续的内存块来快速​​建立索引.deque如果需要链接列表的性能特征,可以使用a .但你最初的前提似乎对我有害.索引插入(标准)链表的中间也很慢.

Answer 3

Python 所说的“列表”实际上并不是链表；而是链表。它们更像是数组。请参阅Python 术语表中的列表条目以及如何在 Python 中创建数组？来自 Python 常见问题解答。

Answer 4

list被实现为数组列表。如果要频繁插入，可以使用a deque（但要注意，遍历到中间的代价是昂贵的）。

或者，您可以使用堆。如果您花时间查看文档，一切都在那里。

Answer 5

Python 列表是使用对其他对象的引用的可调整大小的数组来实现的。与链表实现的 O(n) 查找相比，这提供了 O(1) 查找。

请参阅列表是如何实施的？

正如您所提到的，这种实现使得向 Python 列表的开头或中间的插入变慢，因为插入点右侧的数组中的每个元素都必须移动一个元素。此外，有时必须调整数组大小以容纳更多元素。对于插入到链表中，您仍然需要 O(n) 时间来找到要插入的位置，但实际插入本身将是 O(1)，因为您只需要立即更改节点中的引用插入点之前和之后（假设是双向链表）。

所以让Python列表使用动态数组而不是链表的决定与语言实现的“成熟度”无关。不同数据结构之间存在简单的权衡，Python 的设计者认为动态数组是总体上的最佳选择。他们可能认为对列表进行索引比向列表中插入数据更常见，因此在这种情况下动态数组是更好的选择。

请参阅动态数组维基百科文章中的下表，了解各种数据结构性能特征的比较：

https://en.wikipedia.org/wiki/Dynamic_array#性能