True lists in python?

[Duncan Booth]

Vito 'ZeD' De Tullio <zak.mc.kraken at libero.it> wrote:

> Steven D'Aprano wrote:
> 
>> 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.
> 
> very crude example:
> 
<crude example snipped>

No, you just showed how you can reverse an entire list in constant time. 
The original question and Steven's example were asking to reverse just 
part of the list.

I guess you might be able to do it with a double-linked list provided 
that when traversing the list you always keep two nodes around to 
determine the direction. e.g. instead of asking for node6.nextNode() you 
ask for node6.nextNode(previous=node1) and then the code can return 
whichever sibling wasn't given. That would make reversal (assuming you 
have both nodes) O(1), but would make traversing the list slower.

Also, I don't think it would help if you wanted to implement John 
Nagle's algorithm for the travelling salesman problem: you could hold a 
separate (array based) list of nodes in order to make the random 
selection O(1), but you wouldn't know which direction to follow from 
each node when it comes to cutting the list into 3.


-- 
Duncan Booth http://kupuguy.blogspot.com