[Python-Dev] deque implementation question (original) (raw)

Tim Peters tim.peters at gmail.com
Sun Jul 16 20:09:39 EDT 2017

[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.

More information about the Python-Dev mailing list