list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 22, 12:40 pm, Christian Heimes <li... at cheimes.de> wrote:
> 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?

I wasn't making any assumptions, hence the question mark.  The Python
docs are very good, but even the best of projects make advances that
aren't reflected in the docs.

> 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.
>

I disagree that Python code rarely pops elements off the top of a
list.  There are perfectly valid use cases for wanting a list over a
dequeue without having to pay O(N) for pop(0).  Maybe we are just
quibbling over the meaning of "rarely."

> 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.
>

I am not proposing a linked list of pointers.  I am wondering about
something like this:

p = &p[1];
(and then reclaim p[0] as free memory, I already said I understood
that was the tricky bit)

The pointer arithmetic for accessing each element would still work in O
(1), right?