True lists in python?

[Vito 'ZeD' De Tullio]

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