python - 为什么 Python 的列表没有 shift/unshift 方法？

Question

我想知道为什么 Python 中默认的 list 没有任何 shift、unshift 方法。也许有一个明显的原因，比如列表在内存中的排序方式。

所以目前，我知道我可以使用 append 在列表末尾添加一个项目，并使用 pop 从末尾删除一个元素。但是，我只能使用列表连接来模仿缺少的 shift 或 unshift 方法的行为。

>>> a = [1,2,3,4,5]
>>> a = [0] + a  # Unshift / Push
>>> a
[0,1,2,3,4,5]
>>> a = a[1:]  # Shift / UnPush
>>> a
[1,2,3,4,5]

我错过了什么吗？

Answer 1

Python 列表针对快速固定长度操作进行了优化，并为 pop(0) 和 insert(0, v) 操作带来 O(n) 内存移动成本更改基础数据表示的大小和位置。实际上，CPython 中的“列表”数据类型与许多其他语言可能称为列表(例如链接列表)的工作方式不同 - 它的实现与其他语言可能称为 array 的方式更相似，虽然这里也有一些不同。

您可能对 collections.deque 感兴趣，这是一个类似列表的容器，两端都有快速追加和弹出。

Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

它提供了您似乎在名称 appendleft 下询问的缺失方法和 popleft :

appendleft(x)

Add x to the left side of the deque.

popleft()

Remove and return an element from the left side of the deque.If no elements are present, raises an IndexError.

当然有权衡:在双端队列的中间附近建立索引或插入/删除很慢。事实上 deque.insert(index, object) 甚至是不可能的 before Python 3.5 ，您需要旋转、插入/弹出和旋转回来。双端队列也不支持切片，对于类似的功能，你必须写一些烦人的东西，例如itertools.islice 代替。

关于 deque 与 list 数据结构的优缺点的进一步讨论，请参阅 How are deques in Python implemented, and when are they worse than lists?