list implementation

Heikki Orsila user at host.invalid
Wed Jul 20 14:21:14 CEST 2005

Raymond Hettinger <python at> 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:
heikki.orsila at		"Math is hard, let's go shopping!"

More information about the Python-list mailing list