Vito 'ZeD' De Tullio <zak.mc.kra...@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 -- http://mail.python.org/mailman/listinfo/python-list
