Re: True lists in python?



Dmitry Groshev <lambdadmitry@xxxxxxxxx> 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).
.



Relevant Pages