list implementation

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


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



More information about the Python-list mailing list