Dmitry Groshev <lambdadmi...@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). -- http://mail.python.org/mailman/listinfo/python-list
