list implementation

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