list implementation

[Terry Reedy]

"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

Yes

> 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
> implementation-dependent?

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