> > [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. -- http://mail.python.org/mailman/listinfo/python-list
