Python Data Structures - Doubly Linked List Other Related Topics

Python - Delete odd nodes of the Doubly Linked List



Deleting odd nodes of a doubly linked list requires traverse through the list and deleting odd nodes one by one. If the list is not null then release the head and make next of head as new head. If the new head is not null then make the next of head as null and create two nodes - evenNode and oddNode. Make evenNode to the first even node of list and oddNode to second odd node of the list (3rd node in the original list). If both are not null, delete the oddNode and adjust links. Move both nodes to next set of even-odd nodes. Repeat the process till the any or both nodes become null.

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

def deleteOddNodes(self):  
  if (self.head != None):
    
    #1. if head is not null, make next of head as
    #   new head and delete previous head
    temp = self.head
    self.head = self.head.next
    temp = None
    if (self.head != None):
      
      #2. if the new head is not make prev of head as
      #   null and create nodes - evenNode and oddNode
      self.head.prev = None
      evenNode = self.head
      oddNode = self.head.next 

      while(evenNode != None and oddNode != None):
        
        #3. while evenNode and oddNode are not null
        #   make next of evenNode as next of oddNode
        #   and free oddNode   
        evenNode.next = oddNode.next
        oddNode = None

        #4. and make temp as evenNode and evenNode as 
        #   next of evenNode
        temp = evenNode
        evenNode = evenNode.next
        
        #5. Update prev link, evenNode and oddNode
        if(evenNode != None):
          evenNode.prev = temp
          oddNode = evenNode.next

The below is a complete program that uses above discussed concept of deleting odd nodes of a 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
      return
    else:
      temp = self.head
      while(temp.next != None):
        temp = temp.next
      temp.next = newNode
      newNode.prev = temp

  #delete odd nodes of the list
  def deleteOddNodes(self):  
    if (self.head != None):
      temp = self.head
      self.head = self.head.next
      temp = None
      if (self.head != None):
        self.head.prev = None
        evenNode = self.head
        oddNode = self.head.next 
        while(evenNode != None and oddNode != None):
          evenNode.next = oddNode.next
          oddNode = None
          temp = evenNode
          evenNode = evenNode.next
          if(evenNode != None):
            evenNode.prev = temp
            oddNode = evenNode.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 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