"Book to train programming skills to fight in the world" Python code answer example --2.4 Splitting the list

"Book to train programming skills to fight in the world" Python code answer example --2.4 Splitting the list

CHAP2. Linked list

1. Remove duplicate elements
2. Return Kth from the back
3. Remove elements between
4. Split list
5. Sum of two numbers represented in the list
6. Palindrome
7. Intersecting nodes

Python code answer example

python

from chap2_function import* 

def partition(node,x):
    
    beforeStart = None
    beforeEnd = None

    afterStart = None
    afterEnd = None

    while node:

        next_node = node.next
        node.next = None
        node.prev = None

        if node.data < x:

            if beforeStart == None:
                beforeStart = node
                beforeEnd = beforeStart
            else:
                prev_node = beforeEnd
                beforeEnd.next = node
                beforeEnd = node
                beforeEnd.prev = prev_node

        else:

            if afterStart == None:
                afterStart = node
                afterEnd = afterStart
            else:
                prev_node = afterEnd
                afterEnd.next = node
                afterEnd = node
                afterEnd.prev = prev_node

        node = next_node

    if beforeStart == None:
        return afterStart

    afterStart.prev = beforeEnd
    beforeEnd.next = afterStart

    return beforeStart

dll = DoublyLinkedList() 

# DLL: None -> 3(head) -> 5 -> 8 -> 5 -> 10 -> 2 -> 1(last) -> None 
dll.append(3)  
dll.append(5) 
dll.append(8) 
dll.append(5) 
dll.append(10) 
dll.append(2) 
dll.append(1) 

dll.printList(dll.head) 

partition(dll.head,5)

dll.printList(dll.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