On Sat, 18 Dec 2010 22:18:07 -0800, Dmitry Groshev wrote: > Is there any way to use a true lists (with O(c) insertion/deletion and > O(n) search) in python?
Python lists have amortized constant time insertion and deletion at the end of the list, O(N) insertion and deletion at the beginning of the list, and O(N) search. > For example, to make things like reversing part > of the list with a constant time. It's been many years since I've had to worry about rolling my own low- level linked lists, but I don't think that reversing a list can be done in constant time. I can't see any way to go from this linked list: node1 -> node2 -> node3 -> node4 -> node5 -> node6 -> node7 to this: node1 -> node6 -> node5 -> node4 -> node3 -> node2 -> node7 in constant time. You have to touch each of the nodes being reversed. Others have already suggested you look at deques, but I'm curious as to what application you have where regular lists are too slow. (I assume you have actually profiled your application, and are trying to solve an actual speed issue, not just assuming it is slow.) I would normally reverse a portion of a list like this: mylist[23:42] = mylist[23:42][::-1] So long as the section you are reversing is small enough to fit in memory without paging, this should be quite quick. -- Steven -- http://mail.python.org/mailman/listinfo/python-list
