Efficient Find and Replace

Fredrik Lundh fredrik at pythonware.com
Sat Jan 28 02:09:31 CET 2006

Murali wrote:

> I did not actually run the code, so there may be syntax errors and so
> forth. But how is L[x] = Y an O(1) operation. Given x finding L[x]
> would require to traverse x nodes in the list. So finding L[x] requires
> O(x) time.

no, L[x] is an O(1) operation in both Python and C.

the list type uses an internal array, using over-allocation to make
L.append(x) amortized O(1).


More information about the Python-list mailing list