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.