为什么双端队列实现为链表而不是循环数组？
Why is deque implemented as a linked list instead of a circular array?
CPython deque 是 implemented 作为 64 项大小 "blocks"（数组）的双向链表。这些块都是满的，除了链表两端的块。 IIUC，当 pop / popleft 删除块中的最后一项时，块被释放；当 append/appendleft 尝试添加新项目并且相关块已满时分配它们。
我理解 the listed advantages 使用块链表而不是项目链表：
- 减少每个项目中指向上一个和下一个的指针的内存成本
- 减少每个项目
malloc/free 的运行时成本 added/removed
- 通过将连续的指针彼此相邻放置来改善缓存局部性
但为什么不首先使用单个动态大小的循环数组而不是双向链表呢？
AFAICT，圆形数组将保留上述所有优点，并将 pop*/append* 的（摊销）成本保持在 O(1)（通过过度分配，就像在 list).此外，它将按索引查找的成本从当前的 O(n) 降低到 O(1)。循环数组也更易于实现，因为它可以重用大部分 list 实现。
我可以在 C++ 等语言中看到一个支持链表的论点，其中可以使用指针或迭代器在 O(1) 中从中间删除一个项目；但是，python deque 没有 API 可以做到这一点。
改编自我在 python-dev 邮件列表上的回复：
双端队列的主要目的是使两端的弹出和推送高效。这就是当前实现所做的：无论双端队列中有多少项，每次推送或弹出的最坏情况恒定时间。这在小型和大型中都胜过 "amortized 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
除了接受@TimPeters 的回答外，我还想添加一些不适合评论格式的额外观察结果。
让我们只关注一个常见用例，其中 deque 用作简单的 FIFO 队列。
一旦队列达到其峰值大小，循环数组就不再需要从堆中分配内存。我认为这是一个优势，但事实证明，CPython 实现通过保留可重用内存块列表实现了同样的效果。一条领带。
随着队列大小的增长，循环数组和 CPython 都需要堆中的内存。 CPython 需要一个简单的 malloc，而数组需要（可能更昂贵）realloc（除非原始内存块的右边缘恰好有额外的 space，它需要释放旧内存并复制数据）。 CPython 的优势。
如果队列以比其稳定大小大得多的大小达到峰值，CPython 和数组实现都会浪费未使用的内存（前者将其保存在可重用的块列表中，后者将未使用的内存留空space 在数组中）。一条领带。
正如@TimPeters 指出的那样，对于 CPython，每个 FIFO 队列 put / get 的成本始终是 O(1)，但对于数组只摊销了 O(1)。 CPython 的优势。
CPython deque 是 implemented 作为 64 项大小 "blocks"（数组）的双向链表。这些块都是满的，除了链表两端的块。 IIUC，当 pop / popleft 删除块中的最后一项时，块被释放；当 append/appendleft 尝试添加新项目并且相关块已满时分配它们。
我理解 the listed advantages 使用块链表而不是项目链表：
- 减少每个项目中指向上一个和下一个的指针的内存成本
- 减少每个项目
malloc/free的运行时成本 added/removed - 通过将连续的指针彼此相邻放置来改善缓存局部性
但为什么不首先使用单个动态大小的循环数组而不是双向链表呢？
AFAICT，圆形数组将保留上述所有优点，并将 pop*/append* 的（摊销）成本保持在 O(1)（通过过度分配，就像在 list).此外，它将按索引查找的成本从当前的 O(n) 降低到 O(1)。循环数组也更易于实现，因为它可以重用大部分 list 实现。
我可以在 C++ 等语言中看到一个支持链表的论点，其中可以使用指针或迭代器在 O(1) 中从中间删除一个项目；但是，python deque 没有 API 可以做到这一点。
改编自我在 python-dev 邮件列表上的回复：
双端队列的主要目的是使两端的弹出和推送高效。这就是当前实现所做的：无论双端队列中有多少项，每次推送或弹出的最坏情况恒定时间。这在小型和大型中都胜过 "amortized 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
除了接受@TimPeters 的回答外，我还想添加一些不适合评论格式的额外观察结果。
让我们只关注一个常见用例，其中 deque 用作简单的 FIFO 队列。
一旦队列达到其峰值大小，循环数组就不再需要从堆中分配内存。我认为这是一个优势，但事实证明，CPython 实现通过保留可重用内存块列表实现了同样的效果。一条领带。
随着队列大小的增长，循环数组和 CPython 都需要堆中的内存。 CPython 需要一个简单的 malloc，而数组需要（可能更昂贵）realloc（除非原始内存块的右边缘恰好有额外的 space，它需要释放旧内存并复制数据）。 CPython 的优势。
如果队列以比其稳定大小大得多的大小达到峰值，CPython 和数组实现都会浪费未使用的内存（前者将其保存在可重用的块列表中，后者将未使用的内存留空space 在数组中）。一条领带。
正如@TimPeters 指出的那样，对于 CPython，每个 FIFO 队列 put / get 的成本始终是 O(1)，但对于数组只摊销了 O(1)。 CPython 的优势。