Nov-07-2016, 11:52 AM
(Nov-07-2016, 11:25 AM)wavic Wrote: Fast indexing, fast adding elements to both sides.Those aren't the same thing. A deque is a doubly linked list allowing constant time insertion and extraction at the beginning or end. But getting an element by index is a linear time operation as you need to iterate through links to get to it.
From here https://wiki.python.org/moin/TimeComplexity:
Quote:A deque (double-ended queue) is represented internally as a doubly linked list. (Well, a list of arrays rather than objects, for greater efficiency.) Both ends are accessible, but even looking at the middle is slow, and adding to or removing from the middle is slower still.