Python - Delete first node by key of the Doubly Linked List
In this method, first node in the doubly linked list with specified key (value) is deleted. For example - if the given List is 10->20->30->10->20 and the first occurrence of 20 is deleted, the List becomes 10->30->10->20.
First, the head of the doubly linked list is checked for null value. If the head is not null and the value stored in it is equal to the key, make head next as head, delete previous head, and adjust previous of head. Else, traverse to the node previous to the node with value equal to key, and adjust links.
The function pop_first is created for this purpose. It is a 3-step process.
def pop_first(self, key): temp = self.head #1. check if the head is not null if(temp != None): #2. if head is not null and value stored at head # is equal to the key, make head next as head, # delete previous head, adjust previous of head if(temp.data == key): nodeToDelete = self.head self.head = self.head.next nodeToDelete = None if (self.head != None): self.head.prev = None else: #3. Else, traverse to the node previous to the # node with value equal to key, and adjust links while(temp.next != None): if(temp.next.data == key): nodeToDelete = temp.next temp.next = temp.next.next if(temp.next != None): temp.next.prev = temp nodeToDelete = None break temp = temp.next
The below is a complete program that uses above discussed concept to delete first occurrence of the specified key (if exists) of the doubly linked list.
# node structure class Node: def __init__(self, data): self.data = data self.next = None self.prev = None #class LinkedList 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 newNode.prev = temp #Delete first node by key def pop_first(self, key): temp = self.head if(temp != None): if(temp.data == key): nodeToDelete = self.head self.head = self.head.next nodeToDelete = None if (self.head != None): self.head.prev = None else: while(temp.next != None): if(temp.next.data == key): nodeToDelete = temp.next temp.next = temp.next.next if(temp.next != None): temp.next.prev = temp nodeToDelete = None break 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 the first occurrence of 20 MyList.pop_first(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 20