Efficient Find and Replace
fredrik at pythonware.com
Sat Jan 28 02:09:31 CET 2006
> 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