True lists in python?

[Steven D'Aprano]

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