True lists in python?

[Ulrich Eckhardt]

Dmitry Groshev wrote:
> Is there any way to use a true lists (with O(c) insertion/deletion
> and O(n) search) in python?

Inserting/deleting in the middle requires shuffling elements around, since 
Python's list is an array/vector. If you don't rely on the ordering, insert 
or delete at the end instead, possibly swapping the last element with the 
one you want to delete first:

  class x(list):
      def pop(self, index=None):
          if index is None:
              return list.pop(self)
          res = self[index]
          self[index] = self[-1]
          self.pop()
          return res


> For example, to make things like reversing
> part of the list with a constant time.

a) This doesn't work in constant time but O(n) time.
b) You can have the same complexity with a Python list, too.

Cheers!

Uli