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

Question

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

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

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

Answer 1

在 list -head 上执行 pop 操作时不需要移位，对吗？

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

可以想象另一种实现，其中弹出列表的前面会很便宜（例如deque样式）。我认为我们可以相信这个 Python 文档，并假设这不是内置list类的实现方式。

如果您需要从容器前部有效移除，请使用collections.deque：

双端队列支持从双端队列的任一侧进行线程安全、内存高效的追加和弹出操作，在任一方向上的 O(1) 性能大致相同。

Answer 2

删除第一个元素通常涉及移动所有其他元素，以便前[1]一个元素在[0]删除之后。当然，基于 C 的实现可能只是更改了一个指针，因此数组从第二个元素而不是第一个元素开始，但是它必须跟踪列表开头仍有多少元素可用。