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

Question

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

A deque (double-ended queue) is represented internally as a doubly linked list. (Well, a list of arrays rather than objects, for greater efficiency.) Both ends are accessible, but even looking at the middle is slow, and adding to or removing from the middle is slower still.

两个问题:

1) 是否可以添加到 deque 的中间？我在 API 中看不到任何这样做的方法.

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

Answer 1

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