[Python-Dev] deque implementation question

[Tim Peters]

[Max Moroz <maxmoroz at gmail.com> ]
> What would be the disadvantage of implementing collections.deque as a
> circular array (rather than a doubly linked list of blocks)? ...

You answered it yourself ;-)

> ...
> Of course when the circular array is full, it will need to be reallocated,
> but the amortized cost of that is still O(1).

Bingo.  The primary point of a deque is to make popping and pushing at
both ends efficient.  That's what the current implementation does:
worst-case constant time per push or pop regardless of how many items
are in the deque.  That beats "amortized O(1)" in the small and in the
large.  That's why it was done this way.

Some other deque methods are consequently slower than they are for
lists, but who cares?  For example, the only indices I've ever used
with a deque are 0 and -1 (to peek at one end or the other of a
deque), and the implementation makes accessing those specific indices
constant-time too.