"A book to train programming skills to fight in the world" Python code Solution example --2.5 The sum of two numbers shown in the list

CHAP2. Linked list

Python code answer example

`python`



from chap2_function import* 

def dll_from_node(node): 
  
    dll = DoublyLinkedList()

    while(node is not None): 
        dll.append(node.data) 
        last = node 
        node = node.next

    return dll

   

def addLists(l1,l2,carry):

    if l1==None and l2==None and carry==0:
        return None

    value = carry

    if l1:
        value = value + l1.data
    
    if l2:
        value = value + l2.data

      
    result=Node(value%10)
    
    if l1 or l2:
        more = addLists(None if l1==None else l1.next,
                        None if l2==None else l2.next,
                        1 if value >= 10 else 0
                        )
        result.next = more

    return result

dll_1 = DoublyLinkedList() 

# DLL: None -> 7(head) -> 1 -> 6(last) -> None 
dll_1.append(7)  
dll_1.append(1) 
dll_1.append(6) 

dll_1.printList(dll_1.head) 

dll_2 = DoublyLinkedList() 

# DLL: None -> 7(head) -> 1 -> 6(last) -> None 
dll_2.append(5)  
dll_2.append(9) 
dll_2.append(2) 

dll_2.printList(dll_2.head) 

result_1 = addLists(dll_1.head,dll_2.head,0)

dll_result_1 = dll_from_node(result_1)

dll_result_1.printList(dll_result_1.head)

dll_3 = DoublyLinkedList() 

# DLL: None -> 9(head) -> 9 -> 9(last) -> None 
dll_3.append(9)  
dll_3.append(9) 
dll_3.append(9) 

dll_3.printList(dll_3.head) 

dll_4 = DoublyLinkedList() 

# DLL: None -> 9(head) -> 9 -> 9(last) -> None 
dll_4.append(9)  
dll_4.append(9) 
dll_4.append(9) 

dll_4.printList(dll_4.head) 

result_2 = addLists(dll_3.head,dll_4.head,0)

dll_result_2 = dll_from_node(result_2)

dll_result_2.printList(dll_result_2.head)

Python functions (node class, bidirectional list class)

`chap2_function.py`


#Node class
class Node: 
  
    #constructor
    def __init__(self, data): 
        self.data = data 
        self.next = None
        self.prev = None
  
#Bidirectional list class
class DoublyLinkedList: 
  
    #constructor
    def __init__(self): 
        self.head = None
  
    #Node insertion from the first node
    def push(self, new_data): 
  
        #Node generation
        new_node = Node(new_data) 
  
        #Make the next node of the new node the head node in the first place
        new_node.next = self.head 
  
        #Although it was a head node in the first place, the previous node is changed to a new node
        if self.head is not None: 
            self.head.prev = new_node 
  
        #Make the new node a head node
        self.head = new_node 
  
    #Insert node at intermediate point
    def insert(self, prev_node, new_data): 
  
        # prev_Specify whether to insert the node after the node specified by node
        #If None, exit the function
        if prev_node is None: 
            print("the given previous node cannot be NULL")
            return 
  
        #Node generation
        new_node = Node(new_data) 
  
        #Prev the next node of the new node_Make it the next node of the node specified by node
        new_node.next = prev_node.next
  
        # prev_Makes the next node of the node specified by node a new node
        prev_node.next = new_node 
  
        #Prev the previous node of the new node_Make it the node specified by node
        new_node.prev = prev_node 
  
        #Prev the next node of the new node_I made it the next node of the node specified by node, but the previous node of that node is also made a new node
        if new_node.next is not None: 
            new_node.next.prev = new_node 
  
    #Insert node from last node
    def append(self, new_data): 
  
        #Node generation
        new_node = Node(new_data) 
  
        #Define the next node of the new node to None
        new_node.next = None
  
        #If no head node is set (empty list), set a new node as the head node
        if self.head is None: 
            new_node.prev = None
            self.head = new_node 
            return 
  
        #Set the final node (forward scanning)
        last = self.head 
        while(last.next is not None): 
            last = last.next
  
        #Designate a new node as the last node
        last.next = new_node 
  
        # 7.Make the previous node of the new node the last node in the first place
        new_node.prev = last 
  
        return
  
    def delete(self,del_node):

        if self.head == None or del_node == None: 
            return 

        if self.head == del_node: 
            self.head = del_node.next

        if del_node.next != None: 
            del_node.next.prev = del_node.prev 

        if del_node.prev != None: 
            del_node.prev.next = del_node.next

    def printList(self, node): 
  
        print("Bidirectional list: \n") 

        print("Forward scanning")
        while(node is not None): 
            print(node.data,end="") 
            last = node 
            node = node.next
            if node:
                print(" -> ",end="")
            else:
                print("\n")
  
        print("Reverse scanning")
        while(last is not None): 
            print(last.data,end="")
            last = last.prev 
            if last:
                print(" -> ",end="")
            else:
                print("\n")
  
if __name__ == '__main__':
    #Generate an empty bidirectional list
    # DLL: None
    dll = DoublyLinkedList() 
    # DLL: None -> 6(head/last) -> None
    dll.append(6) 
    # DLL: None -> 7(head) -> 6(last) -> None 
    dll.push(7) 
    # DLL: None -> 1(head) -> 7 -> 6(last) -> None 
    dll.push(1) 
    # DLL: None -> 1(head) -> 7 -> 6 -> 4(last) -> None 
    dll.append(4) 
    # DLL: None -> 1(head) -> 7 -> 8 -> 6 -> 4(last) -> None 
    dll.insert(dll.head.next, 8) 
    # DLL: None -> 1(head) -> 8 -> 6 -> 4(last) -> None 
    dll.delete(dll.head.next) 
    dll.printList(dll.head)

References

[1] GeeksforGeeks: Doubly Linked List | Set 1 (Introduction and Insertion) [2] GeeksforGeeks: Delete a node in a Doubly Linked List