list implementation

[Raymond Hettinger]

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

Yes.


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

Yes.


> 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().

  http://docs.python.org/tut/node13.html#SECTION0013700000000000000000
  http://docs.python.org/lib/module-collections.html


Raymond