python - 是否需要移动才能在 Python 中弹出列表的前面？

Question

python数据结构页面http://docs.python.org/tutorial/datastructures.html说

也可以将列表用作队列，其中添加的第一个元素是检索到的第一个元素(“先进先出”)；然而，列表对于这个目的来说效率不高。虽然从列表末尾追加和弹出是很快的，但是从列表的开头插入或弹出是很慢的(因为所有其他元素都必须移动一个)。

我能理解为什么在列表的前面插入会效率低下。但是为什么它说弹出列表的头部/开头很慢？在 list -head 处执行 pop 操作时不需要移位，对吗？

Answer 1

No shifting is required while doing a pop operation at the list -head right?

将列表视为引用数组，其中列表的第一个元素始终位于数组位置零。当您弹出列表的第一个元素时，您必须将所有引用向左移动一个位置。

人们可以想象替代实现，其中弹出列表的前面会很便宜(例如 deque -style)。我认为我们可以相信关于这方面的 Python 文档，并假设这不是内置 list 类的实现方式。

如果您需要从容器前端高效移除，请使用 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.