python - 为什么 deque 实现为链表而不是循环数组？

Question

CPython deque 是 implemented作为 64 项大小的“ block ”(数组)的双向链表。 block 都是满的，除了链表两端的 block 。 IIUC，当 pop/popleft 删除 block 中的最后一项时， block 被释放；当 append/appendleft 尝试添加新项目并且相关 block 已满时分配它们。

我了解 the listed advantages使用 block 的链表而不是项目的链表:

• 减少每个项目中指向 prev 和 next 的指针的内存成本
• 减少为添加/删除的每个项目执行 malloc/free 的运行时成本
• 通过将连续指针彼此相邻放置来提高缓存局部性

但是为什么一开始不使用单个动态大小的循环数组来代替双向链表呢？

AFAICT，循环数组将保留上述所有优点，并在 O(1) 处保持 pop*/append* 的(摊销)成本(通过过度分配，就像在 list 中一样)。此外，它将提高从当前 O(n) 到 O(1) 的索引查找成本。循环数组也更容易实现，因为它可以重用大部分 list 实现。

我可以在像 C++ 这样的语言中看到一个支持链表的论点，其中从中间删除一个项目可以在 O(1) 中使用指针或迭代器完成；但是，python deque 没有 API 可以做到这一点。

Answer 1

改编 self 在 python-dev 邮件列表上的回复:

双端队列的主要目的是使两端的弹出和推送高效。这就是当前实现所做的:无论双端队列中有多少项，每次推送或弹出的最坏情况恒定时间。这在小型和大型方面都超过了“摊销 O(1)”。这就是为什么这样做的原因。

因此，其他一些双端队列方法比列表慢，但谁在乎呢？例如，我曾经在双端队列中使用过的唯一索引是 0 和 -1(用于查看双端队列的一端或另一端)，并且该实现也使访问这些特定索引的时间保持不变。

事实上，Jim Fasarakis Hilliard 在他的评论中引用了 Raymond Hettinger 的信息:

https://www.mail-archive.com/python-dev@python.org/msg25024.html

确认

The only reason that __getitem__ was put in was to support fast access to the head and tail without actually popping the value