list implementation

sj seungwjun at
Mon Jul 18 04:59:34 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.  That said, I have the following questions:

1. Am I correct in saying the above?

2. Implementing list as an array is part of language specification or

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?


More information about the Python-list mailing list