python数据结构页面http://docs.python.org/tutorial/datastructures.html说
也可以将列表用作队列,其中添加的第一个元素是检索到的第一个元素(“先进先出”);但是,列表对此目的无效。虽然从列表末尾追加和弹出很快,但从列表开头插入或弹出很慢(因为所有其他元素都必须移动一个)。
我可以理解为什么在列表前面进行插入会效率低下。但是为什么它说弹出列表的开头/开头很慢?在 list -head 上执行 pop 操作时不需要移位,对吗?
python数据结构页面http://docs.python.org/tutorial/datastructures.html说
也可以将列表用作队列,其中添加的第一个元素是检索到的第一个元素(“先进先出”);但是,列表对此目的无效。虽然从列表末尾追加和弹出很快,但从列表开头插入或弹出很慢(因为所有其他元素都必须移动一个)。
我可以理解为什么在列表前面进行插入会效率低下。但是为什么它说弹出列表的开头/开头很慢?在 list -head 上执行 pop 操作时不需要移位,对吗?
在 list -head 上执行 pop 操作时不需要移位,对吗?
将列表视为引用数组,其中列表的第一个元素始终位于数组位置为零。当您弹出列表的第一个元素时,您必须将所有引用向左移动一个位置。
可以想象另一种实现,其中弹出列表的前面会很便宜(例如deque样式)。我认为我们可以相信这个 Python 文档,并假设这不是内置list
类的实现方式。
如果您需要从容器前部有效移除,请使用collections.deque
:
双端队列支持从双端队列的任一侧进行线程安全、内存高效的追加和弹出操作,在任一方向上的 O(1) 性能大致相同。
删除第一个元素通常涉及移动所有其他元素,以便前[1]
一个元素在[0]
删除之后。当然,基于 C 的实现可能只是更改了一个指针,因此数组从第二个元素而不是第一个元素开始,但是它必须跟踪列表开头仍有多少元素可用。