Efficient Find and Replace

[Fredrik Lundh]

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).

</F>