transforming a list into a string

[Tim Peters]

[Terry Reedy]
> 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.)

Didn't happen -- it would have been too disruptive to the basic list
type.  Instead, Raymond Hettinger added a cool new dequeue type for
2.4, with O(1) inserts and deletes at both ends, regardless of access
pattern (all the hacks suggested for the base list type appeared to
suffer under *some* pathological (wrt the hack in question) access
pattern).  However, general indexing into a deque is O(N) (albeit with
a small constant factor).  deque[0] and deque[-1] are O(1).

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

Lists and tuples and array.arrays are contiguous vectors, dicts are
hash tables.  Everything follows from that in obvious ways -- butyou
already knew that.  The *language* doesn't guarantee any of it,
though; that's just how CPython is implemented.  FYI, the deque type
is implemented as a doubly-linked list of blocks, each block a
contiguous vector of (at most) 46 elements.