Thanks for the replies. I always thought that Python lists were actually lists under the hood. If they are implemented as arrays of pointers things should be a lot more efficient. In particular what I thought was a Linear-time operation is actually an O(1) operation.
Since python allows you to replace single items with lists e.g. L[x:x+1]= ["a","b","c"], It has to be a little more clever. But with good data structure design I beleive that this overhead can be amortized to O(1). The optional argument to lst.index also makes that an linear time code. Thanks for all the help. - Murali PS: Slowly python is becoming my more favourite language than even C (except in cases you just cannot use anything but C, e.g. writing a boot loader) -- http://mail.python.org/mailman/listinfo/python-list
