list implementation

Raymond Hettinger python at
Mon Jul 18 07:40:50 CEST 2005

> I believe the type "list" is implemented as an array of pointers.


> Thus, random access is an O(1) operation while insertion/deletion is an
> O(n) operation.


> 2. Implementing list as an array is part of language specification or
> implementation-dependent?

Implementation dependent but likely to be an array of pointers.

> 3. What if I actually need a doubly-linked list for constant-time
> insertion/deletion?  Is there a built-in type or a standard class?

Yes.  Use collections.deque().


More information about the Python-list mailing list