Python - Delete all nodes by key of the Linked List
In this method, all nodes in the linked list with specified key (value) is deleted. For example - if the given List is 10->20->30->10->20 and all occurrences of 20 is deleted, the Linked List becomes 10->30->10.
If the head of the linked list is not null and the value stored at head is equal to key, then adjust the head as head next and delete previous head. Keep on doing the same process until the new head becomes null or not equal to the key. After that create a temp node to traverse through the list and delete those nodes with value equal to the key and adjust links accordingly.
The function pop_all is created for this purpose. It is a 2-step process.
def pop_all(self, key): #1. if the head is not null and value stored at # head is equal to key, keep on adjusting the # head as head next and deleting previous head # until new head becomes null or not equal to key while(self.head != None and self.head.data == key): nodeToDelete = self.head self.head = self.head.next nodeToDelete = None #2. create a temp node to traverse through the # list and delete nodes with value equal to # key and adjust links accordingly temp = self.head if(temp != None): while(temp.next != None): if(temp.next.data == key): nodeToDelete = temp.next temp.next = temp.next.next nodeToDelete = None else: temp = temp.next
The below is a complete program that uses above discussed concept to delete all occurrences of the specified key (if exists) of the linked list.
# node structure class Node: def __init__(self, data): self.data = data self.next = None #class Linked List class LinkedList: def __init__(self): self.head = None #Add new element at the end of the list def push_back(self, newElement): newNode = Node(newElement) if(self.head == None): self.head = newNode return else: temp = self.head while(temp.next != None): temp = temp.next temp.next = newNode #Delete all nodes by key def pop_all(self, key): while(self.head != None and self.head.data == key): nodeToDelete = self.head self.head = self.head.next nodeToDelete = None temp = self.head if(temp != None): while(temp.next != None): if(temp.next.data == key): nodeToDelete = temp.next temp.next = temp.next.next nodeToDelete = None else: temp = temp.next #display the content of the list def PrintList(self): temp = self.head if(temp != None): print("The list contains:", end=" ") while (temp != None): print(temp.data, end=" ") temp = temp.next print() else: print("The list is empty.") # test the code MyList = LinkedList() #Add five elements at the end of the list. MyList.push_back(10) MyList.push_back(20) MyList.push_back(30) MyList.push_back(10) MyList.push_back(20) MyList.PrintList() #Delete all occurrences of 20 MyList.pop_all(20) MyList.PrintList()
The above code will give the following output:
The list contains: 10 20 30 10 20 The list contains: 10 30 10