list.pop(0) vs. collections.dequeue

[Chris Rebert]

On Fri, Jan 22, 2010 at 11:14 AM, Steve Howell <showell30 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.

Cheers,
Chris
--
http://blog.rebertia.com