"A book to train programming skills to fight in the world" Python code answer example --2.2 Returns the Kth from the back

"A book to train programming skills to fight in the world" Python code answer example --2.2 Returns the Kth from the back

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 printKthToLast(head_node,k):

    if head_node == None:
        return 0

    index = printKthToLast(head_node.next,k) + 1

    if index == k:
        print(str(k)+"th to last node is "+str(head_node.data))

    return index


dll = DoublyLinkedList() 

# DLL: None -> 1(head) -> 7 -> 4 -> 6 -> 4(last) -> None 
dll.append(6)  
dll.push(7) 
dll.push(1) 
dll.append(4) 
dll.insert(dll.head.next, 4) 

dll.printList(dll.head) 

printKthToLast(dll.head,2)

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 waypoint
    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_Make 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

Recommended Posts

"A book to train programming skills to fight in the world" Python code answer example --2.2 Returns the Kth from the back
"A book to train programming skills to fight in the world" Python code answer example --1.8 "0" matrix
"A book to train programming skills to fight in the world" Python code answer example --3.1 Three stacks
"Book to train programming skills to fight in the world" Python code answer example --1.3 URLify
"Book to train programming skills to fight in the world" Python code answer example --2.6 palindrome
"A book to train programming skills to fight in the world" Python code answer example --1.9 Rotation of strings
"A book to train programming skills to fight in the world" Python code answer example --1.1 Duplicate character string
"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.7 intersecting nodes
"A book to train programming skills to fight in the world" Python code Solution example --1.6 String compression
"A book to train programming skills to fight in the world" Python code Solution example --1.7 Matrix rotation
"Book to train programming skills to fight in the world" Python code answer example --1.4 Permutation of sentences
"A book to train programming skills to fight in the world" Python code Solution example --2.8 Loop detection
"A book to train programming skills to fight in the world" Python code answer example --1.2 Count the number of the same characters
"Book to train programming skills to fight in the world" Python code solution example --- Removed elements between 2.3
"Book to train programming skills to fight in the world" Python code Solution example --2.1 Remove duplicate elements
"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
Programming to fight in the world ~ 5-1
Programming to fight in the world 5-3
Programming to fight in the world ~ 5-2
Programming to fight in the world-Chapter 4
[Kenchon book to Python] "Train your problem-solving skills! Algorithms and data structures" I tried to rewrite the posted code in Python! -table of contents-
An example of the answer to the reference question of the study session. In python.
[Kenchon book to Python]-Chapter 2- "Train your problem-solving skills! Algorithms and data structures" I rewrote the posted code to Python!
[Kenchon book to Python]-Chapter 4-"Train your problem-solving skills! Algorithms and data structures" I rewrote the posted code to Python!
I searched for the skills needed to become a web engineer in Python
Try to solve the programming challenge book with python3
How to create a kubernetes pod from python code
[Python] Programming to find the number of a in a character string that repeats a specified number of times.
How to quickly count the frequency of appearance of characters from a character string in Python?
A Python program in "A book that gently teaches difficult programming"
How to slice a block multiple array from a multiple array in Python
How to use the __call__ method in a Python class
Change the standard output destination to a file in Python
How to get the last (last) value in a list in Python
Extract the value closest to a value from a Python list element
[Python] PCA scratch in the example of "Introduction to multivariate analysis"
How to check the memory size of a variable in Python
From building a Python environment for inexperienced people to Hello world
How to get a string from a command line argument in python
I wrote the code to write the code of Brainf * ck in python
[Introduction to Python] How to use the in operator in a for statement?
How to check the memory size of a dictionary in Python
Simple code to call a python program from Javascript on EC2
From installing Ansible to building a Python environment in Vagrant's virtual environment
Read a file in Python with a relative path from the program
A script that returns 0, 1 attached to the first Python prime number
Change the active version in Pyenv from anaconda to plain Python
How to run the practice code of the book "Creating a profitable AI with Python" on Google Colaboratory
Python programming: I tried to get company information (crawling) from Yahoo Finance in the US using BeautifulSoup4
I tried to refactor the template code posted in "Getting images from Flickr API with Python" (Part 2)