[Python-Dev] deque implementation question (original) (raw)
Max Moroz maxmoroz at gmail.com
Sat Jul 15 03:01:36 EDT 2017
- Previous message (by thread): [Python-Dev] Articles on my contributions to CPython during 2017 Q1 and Q2
- Next message (by thread): [Python-Dev] deque implementation question
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
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 -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://mail.python.org/pipermail/python-dev/attachments/20170715/7910dcb5/attachment.html>
- Previous message (by thread): [Python-Dev] Articles on my contributions to CPython during 2017 Q1 and Q2
- Next message (by thread): [Python-Dev] deque implementation question
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]