Python - Delete last node by key of the Doubly Linked List

In this method, last node in the 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 doubly 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 != None):
      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):
        self.head = self.head.next
        lastNode = None
      else:
        previousToLast.next = lastNode.next
        if(previousToLast.next != None):
          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 doubly linked list.

# node structure
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None
    self.prev = None

#class LinkedList
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 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 != None):
        if(temp.next.data == key):
          previousToLast = temp
          lastNode = temp.next
        temp = temp.next

      if(lastNode != None):
        if(lastNode == self.head):
          self.head = self.head.next
          lastNode = None
        else:
          previousToLast.next = lastNode.next
          if(previousToLast.next != None):
            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 (temp != None):
        print(temp.data, end=" ")
        temp = temp.next
      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 the 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