# Python - Delete last node by key of the Circular Doubly Linked List

In this method, last node in the circular doubly linked list with specified key (value) is deleted. For example - if the given list is 10->20->30->20->40 and the last occurrence of 20 is deleted, the list becomes 10->20->30->40.

If the head of the circular singly linked list is not null, create three nodes: 1. *lastNode* - to track the last node with value equal to key, 2. *previousToLast* - to track node previous to lastNode, and 3. *temp* - to traverse through the list. Then traverse the list to its end while updating *lastNode* and *previousToLast* whenever find a node with value equal to the specified key. At last delete *lastNode* and update links accordingly.

The function *pop_last* is created for this purpose. It is a **3-step process**.

def pop_last(self, key): #1. if head is not null create three nodes # lastNode - to track last node with value # equal to key, previousToLast - to track # node previous to lastNode, temp - to # traverse through the list if(self.head != None): temp = None previousToLast = None lastNode = None #2. traverse through the list and keep on updating # lastNode and previousToLast whenever find a node # with value equal to the specified key if(self.head.data == key): lastNode = self.head temp = self.head while(temp.next != self.head): if(temp.next.data == key): previousToLast = temp lastNode = temp.next temp = temp.next #3. Delete the lastNode and update all links if(lastNode != None): if(lastNode == self.head): if(self.head.next == self.head): self.head = None else: self.head.prev.next = self.head.next self.head = self.head.next lastNode = None else: previousToLast.next = lastNode.next previousToLast.next.prev = previousToLast lastNode = None

The below is a complete program that uses above discussed concept to delete last occurrence of the specified key (if exists) of the circular doubly linked list.

# node structure class Node: def __init__(self, data): self.data = data self.next = None self.prev = 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 newNode.next = self.head newNode.prev = self.head return else: temp = self.head while(temp.next != self.head): temp = temp.next temp.next = newNode newNode.next = self.head newNode.prev = temp self.head.prev = newNode #Delete last node by key def pop_last(self, key): if(self.head != None): temp = None previousToLast = None lastNode = None if(self.head.data == key): lastNode = self.head temp = self.head while(temp.next != self.head): if(temp.next.data == key): previousToLast = temp lastNode = temp.next temp = temp.next if(lastNode != None): if(lastNode == self.head): if(self.head.next == self.head): self.head = None else: self.head.prev.next = self.head.next self.head = self.head.next lastNode = None else: previousToLast.next = lastNode.next previousToLast.next.prev = previousToLast lastNode = None #display the content of the list def PrintList(self): temp = self.head if(temp != None): print("The list contains:", end=" ") while (True): print(temp.data, end=" ") temp = temp.next if(temp == self.head): break 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(20) MyList.push_back(40) MyList.PrintList() #Delete last occurrence of 20 MyList.pop_last(20) MyList.PrintList()

The above code will give the following output:

The list contains: 10 20 30 20 40 The list contains: 10 20 30 40