list implementation
sj
seungwjun at gmail.com
Sun Jul 17 22:59:34 EDT 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
implementation-dependent?
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?
Thanks.
More information about the Python-list
mailing list