Deleting the first element of a list

[Peter Hansen]

Bruce Dawson wrote:
> Then it should be much better to go:
> 
> myList.reverse()
> while myList:
>     # Do Something with the last element
>     del myList[len(myList)-1]
> 
> This changes it from O(n^2) to O(n), which could make it run thousands 
> of times faster.

You're making assumptions, possibly good ones, about the implementation
of the list object in Python.  It's possible, though obviously unlikely,
that the list is reallocated and copied every time it shrinks by even
one element.  (I'm just pointing this out for discussion purposes...
no doubt it doesn't work that way.)  That would leave it at O(n^2).

Unless you profiled this already under a particular implementation of
Python and are sure it really is a question of O(n) vs. O(n^2)...

Likewise, even with the original question, it's possible that for
del list[0] vs. list = list[1:] the overhead of allocating a new
list and deallocating the old one is negligible compared to the
cost of copying n-1 references around in memory.  In that case there
would be only minor performance differences between them for
suitable values of n.

-Peter

Disclaimer: the above may contain bizarre misspellings.  Apparently
late-night dyslexia led me to write "dellocating" and "deglegible",
and I couldn't figure out the correct spellings for a while... there
may still be others lurking.  Yikes...