>But how is L[x] = Y an O(1) operation. Given x finding L[x] would require to >traverse x nodes in the list.
Python list is a deceptive name, because they are 1D arrays of pointers. Maybe they are called lists because array(...) is shorter than list(...). Bye, bearophile -- http://mail.python.org/mailman/listinfo/python-list
