Python deque:与列表的区别？

Question

我正在阅读Python文档:我不明白双端队列如何与列表不同.从文档:

返回从左到右初始化的新deque对象(使用append())和来自iterable的数据.如果未指定iterable,则新的deque为空.

Deques是堆栈和队列的概括(名称发音为"deck",是"双端队列"的缩写).Deques支持线程安全,内存有效的附加和从双端队列的弹出,在任一方向上具有大致相同的O(1)性能.

尽管列表对象支持类似的操作,但它们针对快速固定长度操作进行了优化,并导致pop(0)和insert(0,v)操作的O(n)内存移动成本,这些操作改变了底层数据表示的大小和位置.

如果deque基本上是一个列表,但效率更高,为什么会使用列表代替双端队列呢？

Answer 1

deque更有效地从末端推动和弹出.请继续阅读,并在您将找到的方法列表下方:

索引访问在两端都是O(1),但在中间减慢到O(n).对于快速随机访问,请改用列表.

添加到列表的开头或从列表的开头删除是O(n),但从中间获取元素是O(1).对于双端队列,情况恰恰相反.

所以一般来说,当你不关心中间的东西时,你只需要一个双端队列; 你想以某种顺序喂它,然后在其他地方按顺序取回它们.

Answer 2

Deque是一个双向链表，而List只是一个数组。

随机访问索引 i 处的对象是 O(n) forDeque但 O(1) for List。

开头的快速插入和删除是Deque. 快速随机读取是List.

如果插入和删除在容器中间随机发生，Deque则必须找到节点（O（n），然后插入一个新节点（O（1）），同时List必须移动一些节点（O（n））。

他们都有自己的用例。