list.pop(0) vs. collections.dequeue

[Roy Smith]

In article <mailman.1283.1264192814.28905.python-list at python.org>,
 Christian Heimes <lists 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?
> 
> 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.

Well, at least in theory you could make pop(0) run in O(1).  All you need 
to do is have each list store an offset.  Initially it's 0, and pop(0) 
would just increment the offset.  Then, all references to alist[i] would 
turn into array[i+offset].

Of course, that's a lot of complexity to optimize a relatively rare use 
case.  You're probably better off just using a dequeue :-)