python at rcn.com
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 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