[Python-Dev] deque implementation question

[Max Moroz]

What would be the disadvantage of implementing collections.deque as a
circular array (rather than a doubly linked list of blocks)? My naive
thinking was that a circular array would maintain the current O(1) append/pop
from either side, and would improve index lookup in the middle from O(n) to
O(1). What am I missing?

The insertion/removal of an arbitrary item specified by a pointer would
increase from constant time to linear, but since we don't have pointers
this is a moot point.

Of course when the circular array is full, it will need to be reallocated,
but the amortized cost of that is still O(1). (Moreover, for a bounded
deque, there's even an option of preallocation, which would completely
eliminate reallocations.)

Thanks

Max
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-dev/attachments/20170715/7910dcb5/attachment.html>