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

In this method, first node 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 the first occurrence of 20 is deleted, the list becomes 10->30->10->20.

First, the head of the linked list is checked for null value. If the head is not null, the value stored in it is equal to the key, and head is the only element in the list then make the head as null. If the head is not null, the value stored in it is equal to the key, the list contains more than one element then make head next as head and update the link of last element of the list with the new 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 4-step process.

def pop_first(self, key):
  
  #1. if head is not null, create two nodes- temp,
  #   nodeToDelete - to traverse and to 
  #   track the node to delete  
  if(self.head != None):
    temp = self.head
    nodeToDelete = self.head
    
    #2. if the value store at head is the key and head
    #   is the only element in the list, make it null
    if(temp.data == key):
      if(temp.next == self.head):
        self.head = None
      else:

        #3. if the value store at head is the key and list
        #   contains more than 1 elements, adjust links
        lastNode = self.head.prev
        self.head = self.head.next
        lastNode.next = self.head
        self.head.prev = lastNode
        nodeToDelete = None
    else:
      
      #4. Else, traverse to the node previous to the 
      #   node with value equal to key, and adjust links 
      while(temp.next != self.head):
        if(temp.next.data == key):
          nodeToDelete = temp.next
          temp.next = temp.next.next
          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 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 first node by key
  def pop_first(self, key):
    if(self.head != None):
      temp = self.head
      nodeToDelete = self.head
      if(temp.data == key):
        if(temp.next == self.head):
          self.head = None
        else:
          lastNode = self.head.prev
          self.head = self.head.next
          lastNode.next = self.head
          self.head.prev = lastNode
          nodeToDelete = None
      else:
        while(temp.next != self.head):
          if(temp.next.data == key):
            nodeToDelete = temp.next
            temp.next = temp.next.next
            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 (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 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