Am 19.12.2010 09:24, schrieb Paul Rubin: > 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).
You are both right and both wrong at the same time. Python's deques are neither linked lists nor ordinary lists. They are combination of both techniques. Deques are made of double linked blocks where each block can contain up the 62 Python objects. The type is optimized for push and pop on both sides but not for iteration or search. Christian -- http://mail.python.org/mailman/listinfo/python-list
