Re: list implementation


"sj" <seungwjun@xxxxxxxxx> wrote in message
news:1121655435.153214.292520@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>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



.

Relevant Pages

  • Re: why cannot assign to function call
    ... The Python program deals solely with references; ... when you say "the Python program", ... The value of an array is the ...
    (comp.lang.python)
  • Re: Python vs C for a mail server
    ... > How does type safety tell you anything about the current usage of your ... I find Python to be much ... > circular references). ... That solved easily with non-owning C-style pointers or weak ...
    (comp.lang.python)
  • Re: CFO: Why C?
    ... Renaming pointers to ... >>references doesn't change anything fundamental. ... integer from a byte array is another example. ... Even if I did, the compiler would ...
    (comp.os.linux.development.apps)
  • Re: memory leak problem with arrays
    ... I'm new to programming in python and I hope that this is the problem. ... I've created a cellular automata program in python with the numpy array ... Python keeps track of number of references to every object if the ... I'm not a numpy user. ...
    (comp.lang.python)
  • Re: CFO: Why C?
    ... The difference between pointers and references is more than only a rename. ... Consider a loop over ... an array, where in traditional code often a pointer as well as an index (loop ...
    (comp.os.linux.development.apps)