删除并插入元素以开始列表是否有效？

Question

我在Python网站上发现了这个。

另外，也可以使用一个列表作为队列，其中加入的第一元件 是检索的第一元素（“先入先出”）;但是， 列表不适用于此目的。虽然从 追加和弹出列表的末尾的速度快，这样做从01​​开始插入或弹出的列表是很慢（因为所有其他元素都必须通过一个移位 ）

这是OK但我的问题是，删除或插入元素到列表的开头是否有效？

Answer 1

正如评论者所指出的那样，您从文档中引用的引用明确表示它效率不高。

如果你想要一个有效的双端队列结构，你应该使用deque。

Answer 2

与文档中所述的一样，当您从列表的开头插入或移除元素时，所有其他元素都必须移位，因此对列表大小进行O(n)操作。

但请注意，Python使用引用语义，并且列表的确仅包含指针指向元素，因此只执行指针移动而不移动整个对象。因此，在操作O(n)时，该常数非常小。

例如，在C++中，使用“值语义”代替std::vector（与Python列表最相似的容器）包含对象本身和切换元素，操作更复杂，甚至可能需要复制大量数据少数元素（如果它们很大）。

Answer 3

集合模块中有一个专门设计的容器deque，它在两端更有效地插入和弹出元素。它在其他方面使用与列表相同的方法，所以实现一个队列对象应该保持不变，不带任何副作用，除了使用deque而不是列表。