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]

"sj" <se*******@gmail.com> wrote in message
news:11**********************@o13g2000cwo.googlegr oups.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

[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.ht...00000000000000
http://docs.python.org/lib/module-collections.html
Raymond

[Heikki Orsila]

Raymond Hettinger <py****@rcn.com> wrote:

[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.

--
Heikki Orsila Barbie's law:
he***********@iki.fi "Math is hard, let's go shopping!"
http://www.iki.fi/shd

[Raymond Hettinger]

> > [sj]

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

[Raymond Hettinger] Yes.

[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.