<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On 15 July 2017 at 04:01, Max Moroz <span dir="ltr"><<a href="mailto:maxmoroz@gmail.com" target="_blank">maxmoroz@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto">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 <font face="sans-serif">would maintain the current O(1) </font>append/pop from either side, and would improve index lookup in the middle from O(n) to O(1). What am I missing?<div dir="auto"><br></div><div dir="auto">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.</div><div dir="auto"><br></div><div dir="auto">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.)<br></div></div></blockquote><div><br></div><div>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.</div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><div dir="auto"><div dir="auto"><div dir="auto"><br></div><div dir="auto">Thanks</div><span class="HOEnZb"><font color="#888888"><div dir="auto"><br></div><div dir="auto">Max</div></font></span></div></div></div>
<br>______________________________<wbr>_________________<br>
Python-Dev mailing list<br>
<a href="mailto:Python-Dev@python.org">Python-Dev@python.org</a><br>
<a href="https://mail.python.org/mailman/listinfo/python-dev" rel="noreferrer" target="_blank">https://mail.python.org/<wbr>mailman/listinfo/python-dev</a><br>
Unsubscribe: <a href="https://mail.python.org/mailman/options/python-dev/jsbueno%40python.org.br" rel="noreferrer" target="_blank">https://mail.python.org/<wbr>mailman/options/python-dev/<wbr>jsbueno%40python.org.br</a><br>
<br></blockquote></div><br></div></div>