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