list.pop(0) vs. collections.dequeue

[Christian Heimes]

Steve Howell wrote:
> Is that really true in CPython?  It seems like you could advance the
> pointer instead of shifting all the elements.  It would create some
> nuances with respect to reclaiming the memory, but it seems like an
> easy way to make lists perform better under a pretty reasonable use
> case.
> 
> Does anybody know off the top of their head if the "have-to-be-shifted-
> by-one" warning is actually valid?

Why do you think the documentation has such obvious errors?

CPython's list type uses an array of pointers to store its members. The
type is optimized for the most common list operations in Python:
iteration and appending. Python code rarely changes the head or middle
of a list. The dequeue type is an optimized data structure for popping
and inserting data at both ends.

When you list.pop() or list.insert() the pointers in the internal array
must be shifted. appending is much faster because the internal array is
overallocated meaning it contains free slots at the tail of the data
structure. A linked list of pointers requires more memory and iteration
is slower since since it can't utilize the CPU's cache as good as an array.

Christian