transforming a list into a string

Terry Reedy tjreedy at
Sat Jul 31 21:03:18 CEST 2004

"Roy Smith" <roy at> wrote in message
news:roy-982174.13075831072004 at
> >    Are you sure?  Did you consider the complexity of list.pop(0)?
> I'm assuming list.pop() is O(1), i.e. constant time.  Is it not?

Yes, list.pop() (from the end) is O(1) (which is why -1 is the default arg
However, list.pop(0) (from the front) was O(n) thru 2.3.
The listobject.c code has been rewritten for 2.4 and making the latter O(1)
also *may* have been one of the results.  (This was discussed as desireable
but I don't know the result.)

> Of course, one of my pet peeves about Python is that the complexity of
> the various container operations are not documented.

So volunteer a doc patch, or contribute $ to hire someone ;-).

Terry J. Reedy

More information about the Python-list mailing list