transforming a list into a string

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


"Roy Smith" <roy at panix.com> wrote in message
news:roy-982174.13075831072004 at reader1.panix.com...
> >    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