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:
class Node(object):
def __init__(self, value, list):
self.value = value
self.next = self.previous = None
self.list = list
def nextNode(self):
if not self.list.reversed:
return self.next
else:
return self.previous
class LinkedList(object):
def __init__(self):
self.head = None
self.reversed = False
def insertAsHead(self, value):
n = Node(value, self)
n.next = self.head
if self.head is not None:
self.head.previous = n
self.head = n
def main():
ll = LinkedList()
ll.insertAsHead(4)
ll.insertAsHead(3)
ll.insertAsHead(2)
n = ll.head
while n is not None:
n_previous = n
print n.value
n = n.nextNode()
print 'reversed'
ll.reversed = True
n = n_previous
while n is not None:
print n.value
n = n.nextNode()
if __name__ == '__main__':
main()
--
By ZeD
--
http://mail.python.org/mailman/listinfo/python-list
