list implementation

sj seungwjun at gmail.com
Mon Jul 18 04:57:15 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
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