[Python-Dev] deque implementation question (original) (raw)

Joao S. O. Bueno jsbueno at python.org.br
Tue Jul 18 12:08:49 EDT 2017

On 15 July 2017 at 04:01, 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.)

Now - since you are at it, you could possibly mine pypi for interesting efficient data structures that could cover use cases lists and deque not suffice. I am pretty sure one could find a couple, - and once we get a few that are well behaved and somewhat popular, they could be made candidates for inclusion in collections, I guess.

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/ jsbueno%40python.org.br -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://mail.python.org/pipermail/python-dev/attachments/20170718/b953d377/attachment.html>

More information about the Python-Dev mailing list