More on Linked Lists – flattening and unflattening

1. class Node:
2. def __init__(self,data,prev=None,next=None,child=None):
3. self.data=data
4. self.prev=prev
5. self.next=next
6. self.child=child
8. class ListFlattener:
9. """
10. >>> node1=Node(1)
11. >>> node5=Node(5)
12. >>> node1.child=node5
13. >>> node2=Node(2)
14. >>> node3=Node(3,node1,None,node2)
15. >>> node1.next=node3
16. >>> node4=Node(4,node2)
17. >>> node2.next=node4
18. >>> ListFlattener.listAsArray(node1)
19. [1, 3]
20. >>> ListFlattener.flattenList(node1)
21. >>> ListFlattener.listAsArray(node1)
22. [1, 3, 5, 2, 4]
23. >>> ListFlattener.unflattenList(node1)
24. >>> ListFlattener.listAsArray(node1)
25. [1, 3]
26. >>> ListFlattener.flattenList(node1)
27. >>> ListFlattener.listAsArray(node1)
28. [1, 3, 5, 2, 4]
29. >>> ListFlattener.listAsArray(ListFlattener.findTail(node1),False)
30. [4, 2, 5, 3, 1]
31. """
32. @staticmethod
33. def flattenList(head):
34. curr=head
35. tail=ListFlattener.findTail(head)
36. while curr!=None:
37. if curr.child!=None:
38. tail=ListFlattener.appendChildToEnd(curr,curr.child,tail)
39. curr=curr.next
41. @staticmethod
42. def unflattenList(head):
43. curr=head
44. while curr!=None:
45. if curr.child!=None:
46. curr.child.prev.next=None
47. curr.child.prev=None
48. ListFlattener.unflattenList(curr.child)
49. curr=curr.next
51. @staticmethod
52. def appendChildToEnd(node,child,tail):
53. tail.next=child
54. child.prev=tail
55. return ListFlattener.findTail(child)
57. @staticmethod
58. def findTail(node):
59. while node.next!=None:
60. node=node.next
61. return node
63. @staticmethod
64. def listAsArray(node,forward=True):
65. list=[]
66. while node!=None:
67. list.append(node.data)
68. if forward:
69. node=node.next
70. else:
71. node=node.prev
72. return list
74. if __name__ == "__main__":
75. import doctest
76. doctest.testmod()

class Node:
    def __init__(self,data,prev=None,next=None,child=None):
        self.data=data
        self.prev=prev
        self.next=next
        self.child=child

class ListFlattener:
    """
    >>> node1=Node(1)
    >>> node5=Node(5)
    >>> node1.child=node5
    >>> node2=Node(2)
    >>> node3=Node(3,node1,None,node2)
    >>> node1.next=node3
    >>> node4=Node(4,node2)
    >>> node2.next=node4
    >>> ListFlattener.listAsArray(node1)
    [1, 3]
    >>> ListFlattener.flattenList(node1)
    >>> ListFlattener.listAsArray(node1)
    [1, 3, 5, 2, 4]
    >>> ListFlattener.unflattenList(node1)
    >>> ListFlattener.listAsArray(node1)
    [1, 3]
    >>> ListFlattener.flattenList(node1)
    >>> ListFlattener.listAsArray(node1)
    [1, 3, 5, 2, 4]
    >>> ListFlattener.listAsArray(ListFlattener.findTail(node1),False)
    [4, 2, 5, 3, 1]
    """
    @staticmethod
    def flattenList(head):
        curr=head
        tail=ListFlattener.findTail(head)
        while curr!=None:
            if curr.child!=None:
                tail=ListFlattener.appendChildToEnd(curr,curr.child,tail)
            curr=curr.next

    @staticmethod
    def unflattenList(head):
        curr=head
        while curr!=None:
            if curr.child!=None:
                curr.child.prev.next=None
                curr.child.prev=None
                ListFlattener.unflattenList(curr.child)
            curr=curr.next

    @staticmethod
    def appendChildToEnd(node,child,tail):
        tail.next=child
        child.prev=tail
        return ListFlattener.findTail(child)

    @staticmethod
    def findTail(node):
        while node.next!=None:
            node=node.next
        return node

    @staticmethod
    def listAsArray(node,forward=True):
        list=[]
        while node!=None:
            list.append(node.data)
            if forward:
                node=node.next
            else:
                node=node.prev
        return list

if __name__ == "__main__":
    import doctest
    doctest.testmod()