list implementation

[sj]

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.

 

[Terry Reedy]

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

 

[Raymond Hettinger]

[sj]

I believe the type "list" is implemented as an array of pointers.
Yes.


Thus, random access is an O(1) operation while insertion/deletion is an
O(n) operation.
Yes.


2. Implementing list as an array is part of language specification or
implementation-dependent?

Implementation dependent but likely to be an array of pointers.

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?

Yes. Use collections.deque().

http://docs.python.org/tut/node13.html#SECTION0013700000000000000000
http://docs.python.org/lib/module-collections.html


Raymond

 

[Heikki Orsila]

[sj]

Thus, random access is an O(1) operation while insertion/deletion is an
O(n) operation.

Yes.

Unfortunately no. Check Terry Reeds answer. Random access is O(1),
insertion/deletion to front is O(n), and i/d to back is O(1). The back
i/d operation has amortized O(1) cost.

 

[Raymond Hettinger]

[sj]
[Raymond Hettinger]
[Heikki Orsila aka host.invalid]

Unfortunately no. Check Terry Reeds answer. Random access is O(1),
insertion/deletion to front is O(n), and i/d to back is O(1). The back
i/d operation has amortized O(1) cost.

Duh. Excellent misreading of a simple answer to the OP's plain
question. It is clear from his post that he already had a pretty
accurate guess about how lists were implemented and the consequent
performance implications.

What was needed was a confirmation of his guess and a pointer to
collections.deque() for O(1) insertion/deletion on the ends. For O(1)
length changing ops in the middle, his suggestion of a linked list was
not off base. IOW, a simple yes would have served.


Raymond


P.S. Non-standard abbreviations like, i/d, are rarely helpful to your
readers.