[Python-Dev] deque implementation question
maxmoroz at gmail.com
Sat Jul 15 03:01:36 EDT 2017
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
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Python-Dev