刚学Python。阅读官方教程。我遇到了这个：
虽然从列表末尾追加和弹出很快，但从列表开头插入或弹出很慢（因为所有其他元素都必须移动一个）。
我会猜到像 Python 这样的成熟语言会有各种优化，那么为什么 Python [似乎] 不使用链表来快速插入呢？
问问题
6417 次
5 回答
25
Python 在内存中使用线性列表布局，因此索引速度很快 (O(1))。
于 2012-09-05T03:22:01.390 回答
10
正如 Greg Hewgill 已经指出的那样，python 列表使用连续的内存块来加快索引速度。deque如果您想要链表的性能特征，可以使用 a 。但你最初的前提对我来说似乎有缺陷。到（标准）链表中间的索引插入也很慢。
于 2012-09-05T03:26:52.707 回答
5
list被实现为一个数组列表。如果要频繁插入，可以使用a deque（但要注意遍历到中间很费钱）。
或者，您可以使用堆。如果您花时间查看文档，它就在那里。
于 2012-09-05T03:27:19.090 回答
5
Python 所称的“列表”实际上并不是链表。它们更像是数组。请参阅Python 词汇表中的列表条目以及如何在 Python 中创建数组？来自 Python 常见问题解答。
于 2012-09-05T03:29:02.803 回答
5
Python 列表是使用可调整大小的对其他对象的引用数组来实现的。与链表实现的 O(n) 查找相比，这提供了 O(1) 查找。
请参阅列表是如何实现的？
正如您所提到的，此实现使插入到 Python 列表的开头或中间的速度变慢，因为插入点右侧的数组中的每个元素都必须移动到一个元素上。此外，有时必须调整数组的大小以容纳更多元素。对于插入链表，您仍然需要 O(n) 时间来找到要插入的位置，但实际插入本身将是 O(1)，因为您只需要立即更改节点中的引用在插入点之前和之后（假设是双向链表）。
因此，让 Python 列表使用动态数组而不是链表的决定与语言实现的“成熟度”无关。在不同的数据结构之间存在简单的权衡，Python 的设计者认为动态数组是总体上最好的选择。他们可能认为索引列表比向列表中插入数据更常见，因此在这种情况下使动态数组成为更好的选择。
有关各种数据结构性能特征的比较，请参阅动态数组维基百科文章中的下表：
于 2015-07-03T17:40:16.230 回答