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

Question

我很奇怪,为什么默认listPython中没有任何shift,unshift方法.也许有一个明显的原因,就像列表在内存中的排序方式一样.

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

>>> 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列表针对快速固定长度操作进行了优化,并导致O(n)内存移动成本pop(0)和insert(0, v)操作,从而改变底层数据表示的大小和位置.实际上,CPython中的"list"数据类型与许多其他语言可能称之为列表(例如链接列表)的工作方式不同 - 它的实现方式与其他语言可能称为数组的方式类似,尽管这里也存在一些差异.

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

Deques支持线程安全,内存有效的附加和从双端队列的弹出,在任一方向上具有大致相同的O(1)性能.您似乎要问的遗漏方法是在名称appendleft和提供下提供的popleft:

__PRE__

当然存在权衡,并且在双端队列中间附近的索引或插入/移除是缓慢的.实际上在Python 3.5之前deque.insert(index, object)甚至不可能,你需要旋转,插入/弹出和旋转.你也失去了切片,所以如果你需要的话,你将不得不写一些烦人的东西,比如说. itertools.islice

有关dequevs list数据结构的优缺点的进一步讨论,请参阅如何实现Python中的deques,以及它们何时比列表更糟糕？