On 15 July 2017 at 04:01, Max Moroz wrote:
> 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
[Max Moroz ]
> 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
I found the answer in _collectionsmodule.c
/* Data for deque objects is stored in a doubly-linked list of fixed
* length blocks. This assures that appends or pops never move any
* other data elements besides the one being appended or popped.
*
* Another advantage is that it completely avoids
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).
