On Jan 22, 12:14 pm, Chris Rebert <c...@rebertia.com> wrote: > On Fri, Jan 22, 2010 at 11:14 AM, Steve Howell <showel...@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. -- http://mail.python.org/mailman/listinfo/python-list
