True lists in python?

Christian Heimes lists at cheimes.de
Sun Dec 19 03:58:55 EST 2010


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




More information about the Python-list mailing list