list.pop(0) vs. collections.dequeue

[Christian Heimes]

Arnaud Delobelle wrote:
> I made the comment you quoted.  In CPython, it is O(n) to delete/insert
> an element at the start of the list - I know it because I looked at the
> implementation a while ago.  This is why collections.deque exists I
> guess.  I don't know how they are implemented but insertion/deletion at
> either end are O(1) and so is random access.  So they are the data
> structure that you want.

Your assumption is correct. The collections.dequeue type uses a double
linked list of blocks. Each blocks contains a fixed amount of pointers
to Python objects. The implementation makes the implementation less
memory hungry than a standard double linked list with just one element
for each block.

Christian