为什么在collections.deque中添加或删除比在那里查找更慢？

Question

这个关于某些数据结构的算法复杂性的wiki.python.org页面说明了collections.deque对象的以下内容:

deque(双端队列)在内部表示为双向链表.(好吧,一个数组列表而不是对象,以提高效率.)两端都可以访问,但即使看中间也很慢,中间增加或删除速度较慢.

两个问题:

1)是否可能添加到中间deque？我没有在API中看到任何方法.

2)为什么删除(或添加)比在中间查找要慢deque？它是一个双向链表,因此一旦找到要添加的对象,添加/删除应该是一个恒定时间操作.

Answer 1

1. 可以使用remove()方法或del关键字删除项目。无法插入项目。（唯一可能的插入方式不会出现在 API 文档中是切片分配，这在deque.上是无效的。）
2. 因为，正如描述所说，它实际上是一个数组的双向链表。因此，插入或删除内容可能需要将元素从一个数组移动到另一个数组。（我没有看过实现，但我知道deque在查找元素时使用了步幅技术，我假设所用数组的大小与步幅长度相同，即 62。）您必须移动 alist删除项目时也有大量内存，但至少它全部在一个块中并且可以有效地移动。

Answer 2

可以用python3.5插入。index(), insert(), and copy()三个新方法仅在python3.5，python 3.5 中的新方法中可用，在早期版本中无法插入双端队列：

deque 类现在定义了 index()、insert() 和 copy()，以及支持+和*运算符。这允许将双端队列识别为 MutableSequence 并提高它们对列表的可替换性。（由 Raymond Hettinger 提供，第 23704 期。）

您可以使用del或从双端队列的中间删除deque.remove：

 deq = deque([1,2,3,4,5,6])
 del deq[4] 
 deq.remove(3)