tjreedy at udel.edu
Mon Jul 18 07:02:39 CEST 2005
"sj" <seungwjun at gmail.com> wrote in message
news:1121655435.153214.292520 at o13g2000cwo.googlegroups.com...
>I believe the type "list" is implemented as an array of pointers.
A Python list is sematically/behaviorally defined as a mutable extensible
sequence of references to Python objects. For the CPython reference
implementation, the references are arrays of C pointers. Since, on
balance, this works well, I presume the other four active computer language
implementations do something equivalent. (How we humans execute Python
code is a different question!)
> Thus, random access is an O(1) operation
> while insertion/deletion is an O(n) operation.
At the front, yes. (But modern CPUs with a one-instruction block mem move
make the hidden multiplier relatively small.) At the end of the list, no;
it is O(1). Making front insertion/deletion (but not in the middle) also
O(1) has been considered but so far rejected. (For apps that need the
symmetry, there is collections.deque.)
> 2. Implementing list as an array is part of language specification or
While I believe I have answered this, I recommend reading the relevant
parts of the language and library manuals (see chapter 2 of the latter).
> 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?
I believe it is roll-your-own to your specific needs. Of course, scanning
thru such a list is still O(n).
Terry J. Reedy
More information about the Python-list