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
--
http://mail.python.org/mailman/listinfo/python-list
