# Python - Delete odd nodes of the Circular Doubly Linked List

Deleting odd nodes of a circular doubly linked list requires traverse through the list and deleting odd nodes one by one. It involves the following process. If the list contains only head then make the head null. If the list contains more than one element then delete the head and adjust the link of last element with the new head. If next of head is not head then, create three nodes - *evenNode* pointing to head, *oddNode* pointing to next of head and *temp* to store last even node. Then delete *oddNode* and update *evenNode* and *oddNode* to next set of odd-even nodes and continue the process till any of the node reaches head. After that if *evenNode* reaches head, make next of *temp* as head else make next of *evenNode* as head and adjust other links accordingly.

The function *deleteOddNodes* is created for this purpose. It is a **5-step process**.

def deleteOddNodes(self): #1. if head is the only element element in # list make the head as null if(self.head != None and self.head.next == self.head): self.head = None elif (self.head != None): #2. if the list contains more than one element # delete the head and adjust the link of # last element with the new head temp = self.head while(temp.next != self.head): temp = temp.next temp.next = self.head.next self.head.next.prev = temp self.head = None self.head = temp.next #3. create evenNode node - pointing to head # oddNode node - pointing to next of head # temp node - to store last even node if(self.head != None and self.head.next != self.head): evenNode = self.head oddNode = self.head.next while(True): #4. delete odd node and update evenNode and # oddNode to next set of odd-even nodes update # temp node to latest evenNode node continue # the process till any of the node reaches head temp = evenNode evenNode.next = oddNode.next evenNode.next.prev = evenNode oddNode = None evenNode = evenNode.next oddNode = evenNode.next if(evenNode == self.head or oddNode == self.head): break #5. if evenNode reaches head, make next of temp # as head else make next of evenNode as head # and adjust other links accordingly if(evenNode == self.head): temp.next = self.head self.head.prev = temp else: evenNode.next = self.head self.head.prev = evenNode

The below is a complete program that uses above discussed concept of deleting odd nodes of a 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 odd nodes of the list def deleteOddNodes(self): if(self.head != None and self.head.next == self.head): self.head = None elif (self.head != None): temp = self.head while(temp.next != self.head): temp = temp.next temp.next = self.head.next self.head.next.prev = temp self.head = None self.head = temp.next if(self.head != None and self.head.next != self.head): evenNode = self.head oddNode = self.head.next while(True): temp = evenNode evenNode.next = oddNode.next evenNode.next.prev = evenNode oddNode = None evenNode = evenNode.next oddNode = evenNode.next if(evenNode == self.head or oddNode == self.head): break if(evenNode == self.head): temp.next = self.head self.head.prev = temp else: evenNode.next = self.head self.head.prev = evenNode #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 in the list. MyList.push_back(10) MyList.push_back(20) MyList.push_back(30) MyList.push_back(40) MyList.push_back(50) #Display the content of the list. MyList.PrintList() #delete odd nodes of the list MyList.deleteOddNodes() print("After deleting odd nodes:") #Display the content of the list. MyList.PrintList()

The above code will give the following output:

The list contains: 10 20 30 40 50 After deleting odd nodes: The list contains: 20 40