Python - Delete all nodes by key of the Circular Doubly Linked List

In this method, all nodes in the circular doubly 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 are deleted, the list becomes 10->30->10.

If the head of the circular doubly linked list is not null and the value stored at head is equal to key, then adjust the head as head next, delete previous head and adjust links. 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):
    if(self.head.next == self.head):
      self.head = None
    else:
      nodeToDelete = self.head
      temp = self.head
      
      # traverse to the last element of
      # the list to adjust links
      while(temp.next != self.head):
        temp = temp.next
      self.head = self.head.next
      temp.next = self.head  
      self.head.prev = temp
      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 != self.head):
      if(temp.next.data == key):
        nodeToDelete = temp.next
        temp.next = temp.next.next
        temp.next.prev = temp
        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 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 all nodes by key
  def pop_all(self, key):
    while(self.head != None and self.head.data == key):
      if(self.head.next == self.head):
        self.head = None
      else:
        nodeToDelete = self.head
        temp = self.head
        while(temp.next != self.head):
          temp = temp.next
        self.head = self.head.next
        temp.next = self.head  
        self.head.prev = temp
        nodeToDelete = None

    temp = self.head        
    if(temp != None):
      while(temp.next != self.head):
        if(temp.next.data == key):
          nodeToDelete = temp.next
          temp.next = temp.next.next
          temp.next.prev = temp
          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 (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(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