list.pop(0) vs. collections.dequeue

[Steve Howell]

On Jan 22, 12:14 pm, Chris Rebert <c... at rebertia.com> wrote:
> On Fri, Jan 22, 2010 at 11:14 AM, Steve Howell <showel... at yahoo.com> wrote:
> > The v2.6.4 version of the tutorial says this:
>
> > '''
> > It is also possible to use a list as a queue, where the first element
> > added is the first element retrieved (“first-in, first-out”); however,
> > lists are not efficient for this purpose. While appends and pops from
> > the end of list are fast, doing inserts or pops from the beginning of
> > a list is slow (because all of the other elements have to be shifted
> > by one).
> > '''
>
> > 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?
>
> Judging by the "Sorted dictionary" thread responses: Yes.
>

I think you are referring to this comment:

'''
Insertion and deletion are still O(n) as all items to the right of the
inserted/deleted one have to be shifted by one place.
'''

http://groups.google.com/group/comp.lang.python/browse_thread/thread/d3699724d94d5b5a

I can certainly see why most reasonable implementations of a list
would have insertion/deletion in the middle of the list be O(N), but I
don't think that limitation has to apply for the special cases of the
beginning and end of the list.