Python Data Structures - Circular Doubly Linked List Other Related Topics
Python Java C++ C C# PHP R SQL DS Algo InterviewQ

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 

5