[Python-Dev] deque implementation question

[INADA Naoki]

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 use of realloc(),
 * resulting in more predictable performance.

Regards,
INADA Naoki  <songofacandy at gmail.com>


On Sat, Jul 15, 2017 at 4:01 PM, Max Moroz <maxmoroz at gmail.com> 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 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
>
> _______________________________________________
> Python-Dev mailing list
> Python-Dev at python.org
> https://mail.python.org/mailman/listinfo/python-dev
> Unsubscribe:
> https://mail.python.org/mailman/options/python-dev/songofacandy%40gmail.com
>