True lists in python?

[Paul Rubin]

Dmitry Groshev <lambdadmitry at gmail.com> writes:
> -I can't find any information about reverse's complexity in python
> docs, but it seems that deque is a linked list. Maybe this is the one
> I need.

Deques are not linked lists.  They're just like regular Python lists
(i.e. resizeable arrays) except they can grow and shrink at both ends
rather than just one.  The amortized complexity of an append or pop
operation (at either end) is O(1) but occasionally the list has to
be reallocated, which is O(N).