Data Structures - Circular Doubly Linked List Other Related Topics
Data Structures - Circular Doubly Linked List Other Related Topics

Circular Doubly Linked List - Delete last node by key

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.

void pop_last(int 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(head != NULL) {
    Node *previousToLast, *lastNode, *temp; 
    previousToLast = NULL;
    lastNode = NULL;
    
    //2. traverse through the list and keep on updating
    //   lastNode and previousToLast whenever find a node
    //   with value equal to the specified key
    if(head->data == key) 
      lastNode = head;
    
    temp = head;
    while(temp->next != head) {
      if(temp->next->data == key) {
        previousToLast = temp;
        lastNode = temp->next;
      }
      temp = temp->next;
    }
 
    //3. Delete the lastNode and update all links
    if(lastNode != NULL) {
      if(lastNode == head) {
        if(head->next == head)
          head = NULL;
        else {
          head->prev->next = head->next;
          head = head->next;
        }
        free(lastNode);
      } else {
        previousToLast->next = lastNode->next;
        previousToLast->next->prev = previousToLast;
        free(lastNode);
      }
    }
  }
} 

void pop_last(struct Node** head_ref, int 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(*head_ref != NULL) {
    struct Node *previousToLast, *lastNode, *temp; 
    previousToLast = NULL;
    lastNode = NULL;
    
    //2. traverse through the list and keep on updating
    //   lastNode and previousToLast whenever find a node
    //   with value equal to the specified key
    if((*head_ref)->data == key) 
      lastNode = *head_ref;
    
    temp = *head_ref;
    while(temp->next != *head_ref) {
      if(temp->next->data == key) {
        previousToLast = temp;
        lastNode = temp->next;
      }
      temp = temp->next;
    }
 
    //3. Delete the lastNode and update all links
    if(lastNode != NULL) {
      if(lastNode == *head_ref) {
        if((*head_ref)->next == *head_ref)
          *head_ref = NULL;
        else {
          (*head_ref)->prev->next = (*head_ref)->next;
          *head_ref = (*head_ref)->next;
        }
        free(lastNode);
      } else {
        previousToLast->next = lastNode->next;
        previousToLast->next->prev = previousToLast;
        free(lastNode);
      }
    }
  }
}    

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

void pop_last(int 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(head != null) {
    Node previousToLast, lastNode, temp; 
    previousToLast = null;
    lastNode = null;
    
    //2. traverse through the list and keep on updating
    //   lastNode and previousToLast whenever find a node
    //   with value equal to the specified key
    if(head.data == key) 
      lastNode = head;
    
    temp = head;
    while(temp.next != head) {
      if(temp.next.data == key) {
        previousToLast = temp;
        lastNode = temp.next;
      }
      temp = temp.next;
    }
 
    //3. Delete the lastNode and update all links
    if(lastNode != null) {
      if(lastNode == head) {
        if(head.next == head)
          head = null;
        else {
          head.prev.next = head.next;
          head = head.next;
        }
        lastNode = null;
      } else {
        previousToLast.next = lastNode.next;
        previousToLast.next.prev = previousToLast;
        lastNode = null;
      }
    }
  }
} 

public void pop_last(int 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(head != null) {
    Node previousToLast, lastNode, temp; 
    previousToLast = null;
    lastNode = null;
    
    //2. traverse through the list and keep on updating
    //   lastNode and previousToLast whenever find a node
    //   with value equal to the specified key
    if(head.data == key) 
      lastNode = head;
    
    temp = head;
    while(temp.next != head) {
      if(temp.next.data == key) {
        previousToLast = temp;
        lastNode = temp.next;
      }
      temp = temp.next;
    }
 
    //3. Delete the lastNode and update all links
    if(lastNode != null) {
      if(lastNode == head) {
        if(head.next == head)
          head = null;
        else {
          head.prev.next = head.next;
          head = head.next;
        }
        lastNode = null;
      } else {
        previousToLast.next = lastNode.next;
        previousToLast.next.prev = previousToLast;
        lastNode = null;
      }
    }
  }
}  

public function pop_last($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($this->head != null) {
    $temp = new Node();
    $previousToLast = null;
    $lastNode = null;
    
    //2. traverse through the list and keep on updating
    //   lastNode and previousToLast whenever find a node
    //   with value equal to the specified key
    if($this->head->data == $key) 
      $lastNode = $this->head;
    
    $temp = $this->head;
    while($temp->next != $this->head) {
      if($temp->next->data == $key) {
        $previousToLast = $temp;
        $lastNode = $temp->next;
      }
      $temp = $temp->next;
    }
 
    //3. Delete the lastNode and update all links
    if($lastNode != null) {
      if($lastNode == $this->head) {
        if($this->head->next == $this->head)
          $this->head = null;
        else {
          $this->head->prev->next = $this->head->next;
          $this->head = $this->head->next;
        }
        $lastNode = null;
      } else {
        $previousToLast->next = $lastNode->next;
        $previousToLast->next->prev = $previousToLast;
        $lastNode = null;
      }
    }
  }
}

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.

#include <iostream>
using namespace std;

//node structure
struct Node {
    int data;
    Node* next;
    Node* prev;
};

class LinkedList {
  private:
    Node* head;
  public:
    LinkedList(){
      head = NULL;
    }
 
    //Add new element at the end of the list
    void push_back(int newElement) {
      Node* newNode = new Node();
      newNode->data = newElement;
      newNode->next = NULL;
      newNode->prev = NULL; 
      if(head == NULL) {
        head = newNode;
        newNode->next = head;
        newNode->prev = head;
      } else {
        Node* temp = head;
        while(temp->next != head)
          temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
        newNode->prev = temp;
        head->prev = newNode;
      }    
    }

    //Delete last node by key
    void pop_last(int key) {     
      if(head != NULL) {
        Node *previousToLast, *lastNode, *temp; 
        previousToLast = NULL;
        lastNode = NULL;
        
        if(head->data == key) 
          lastNode = head;
        
        temp = head;
        while(temp->next != head) {
          if(temp->next->data == key) {
            previousToLast = temp;
            lastNode = temp->next;
          }
          temp = temp->next;
        }

        if(lastNode != NULL) {
          if(lastNode == head) {
            if(head->next == head)
              head = NULL;
            else {
              head->prev->next = head->next;
              head = head->next;
            }
            free(lastNode);
          } else {
            previousToLast->next = lastNode->next;
            previousToLast->next->prev = previousToLast;
            free(lastNode);
          }
        }
      }
    } 

    //display the content of the list
    void PrintList() {
      Node* temp = head;
      if(temp != NULL) {
        cout<<"The list contains: ";
        while(true) {
          cout<<temp->data<<" ";
          temp = temp->next;
          if(temp == head) 
            break;
        }
        cout<<endl;
      } else {
        cout<<"The list is empty.\n";
      }
    }     
};

// test the code 
int main() {
  LinkedList MyList;

  //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();

  return 0; 
}

The above code will give the following output: 

The list contains: 10 20 30 20 40 
The list contains: 10 20 30 40 

#include <stdio.h>
#include <stdlib.h>

//node structure
struct Node {
  int data;
  struct Node* next;
  struct Node* prev;
};

//Add new element at the end of the list
void push_back(struct Node** head_ref, int newElement) {  
  struct Node *newNode, *temp;
  newNode = (struct Node*)malloc(sizeof(struct Node)); 
  newNode->data = newElement;  
  newNode->next = NULL;
  newNode->prev = NULL;
  if(*head_ref == NULL) {
    *head_ref = newNode;
     newNode->next = *head_ref;
     newNode->prev = *head_ref;
  } else {
    temp = *head_ref;
    while(temp->next != *head_ref) {
      temp = temp->next;
    }    
    temp->next = newNode;
    newNode->next = *head_ref;
    newNode->prev = temp;
    (*head_ref)->prev = newNode;
  }
}

//Delete last node by key
void pop_last(struct Node** head_ref, int key) {     
  if(*head_ref != NULL) {
    struct Node *previousToLast, *lastNode, *temp; 
    previousToLast = NULL;
    lastNode = NULL;
    
    if((*head_ref)->data == key) 
      lastNode = *head_ref;
    
    temp = *head_ref;
    while(temp->next != *head_ref) {
      if(temp->next->data == key) {
        previousToLast = temp;
        lastNode = temp->next;
      }
      temp = temp->next;
    }
 
    if(lastNode != NULL) {
      if(lastNode == *head_ref) {
        if((*head_ref)->next == *head_ref)
          *head_ref = NULL;
        else {
          (*head_ref)->prev->next = (*head_ref)->next;
          *head_ref = (*head_ref)->next;
        }
        free(lastNode);
      } else {
        previousToLast->next = lastNode->next;
        previousToLast->next->prev = previousToLast;
        free(lastNode);
      }
    }
  }
}   

//display the content of the list
void PrintList(struct Node* head_ref) {
  struct Node* temp = head_ref;
  if(head_ref != NULL) {
    printf("The list contains: ");
    while (1) {
      printf("%i ",temp->data);
      temp = temp->next;
      if(temp == head_ref)
        break;    
    }
    printf("\n");
  } else {
    printf("The list is empty.\n");
  }   
}

// test the code 
int main() {
  struct Node* MyList = NULL;

  //Add five elements at the end of the list.
  push_back(&MyList, 10);
  push_back(&MyList, 20);
  push_back(&MyList, 30);
  push_back(&MyList, 20);
  push_back(&MyList, 40);
  PrintList(MyList);

  //Delete last occurrence of 20
  pop_last(&MyList, 20);
  PrintList(MyList);

  return 0; 
}

The above code will give the following output: 

The list contains: 10 20 30 20 40 
The list contains: 10 20 30 40 

# 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 

//node structure
class Node {
    int data;
    Node next;
    Node prev;
};

class LinkedList {
  Node head;

  LinkedList(){
    head = null;
  }

  //Add new element at the end of the list
  void push_back(int newElement) {
    Node newNode = new Node();
    newNode.data = newElement;
    newNode.next = null; 
    newNode.next = null;
    if(head == null) {
      head = newNode;
      newNode.next = head;
      newNode.prev = head;
    } else {
      Node temp = new Node();
      temp = head;
      while(temp.next != head)
        temp = temp.next;
      temp.next = newNode;
      newNode.next = head;
      newNode.prev = temp;
      head.prev = newNode;
    }    
  }

  //Delete last node by key
  void pop_last(int key) {     
    if(head != null) {
      Node previousToLast, lastNode, temp; 
      previousToLast = null;
      lastNode = null;

      if(head.data == key) 
        lastNode = head;
      
      temp = head;
      while(temp.next != head) {
        if(temp.next.data == key) {
          previousToLast = temp;
          lastNode = temp.next;
        }
        temp = temp.next;
      }

      if(lastNode != null) {
        if(lastNode == head) {
          if(head.next == head)
            head = null;
          else {
            head.prev.next = head.next;
            head = head.next;
          }
          lastNode = null;
        } else {
          previousToLast.next = lastNode.next;
          previousToLast.next.prev = previousToLast;
          lastNode = null;
        }
      }
    }
  } 

  //display the content of the list
  void PrintList() {
    Node temp = new Node();
    temp = this.head;
    if(temp != null) {
      System.out.print("The list contains: ");
      while(true) {
        System.out.print(temp.data + " ");
        temp = temp.next;
        if(temp == this.head)
          break;
      }
      System.out.println();
    } else {
      System.out.println("The list is empty.");
    }
  }     
};

// test the code 
public class Implementation {
  public static void main(String[] args) {
    LinkedList MyList = new 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 

using System;

//node structure
class Node {
  public int data;
  public Node next;
  public Node prev;
};

class LinkedList {
  Node head;

  public LinkedList(){
    head = null;
  }
  
  //Add new element at the end of the list
  public void push_back(int newElement) {
    Node newNode = new Node();
    newNode.data = newElement;
    newNode.next = null; 
    newNode.prev = null;
    if(head == null) {
      head = newNode;
      newNode.next = head;
      newNode.prev = head;
    } else {
      Node temp = new Node();
      temp = head;
      while(temp.next != head)
        temp = temp.next;
      temp.next = newNode;
      newNode.next = head;
      newNode.prev = temp;
      head.prev = newNode;
    }    
  }

  //Delete last node by key
  public void pop_last(int key) {     
    if(head != null) {
      Node previousToLast, lastNode, temp; 
      previousToLast = null;
      lastNode = null;
      
      if(head.data == key) 
        lastNode = head;
      
      temp = head;
      while(temp.next != head) {
        if(temp.next.data == key) {
          previousToLast = temp;
          lastNode = temp.next;
        }
        temp = temp.next;
      }
   
      if(lastNode != null) {
        if(lastNode == head) {
          if(head.next == head)
            head = null;
          else {
            head.prev.next = head.next;
            head = head.next;
          }
          lastNode = null;
        } else {
          previousToLast.next = lastNode.next;
          previousToLast.next.prev = previousToLast;
          lastNode = null;
        }
      }
    }
  }  

  //display the content of the list
  public void PrintList() {
    Node temp = new Node();
    temp = this.head;
    if(temp != null) {
      Console.Write("The list contains: ");
      while(true) {
        Console.Write(temp.data + " ");
        temp = temp.next;
        if(temp == this.head)
          break;        
      }
      Console.WriteLine();
    } else {
      Console.WriteLine("The list is empty.");
    }
  }      
};

// test the code
class Implementation {  
  static void Main(string[] args) {
    LinkedList MyList = new 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 

<?php
//node structure
class Node {
  public $data;
  public $next;
  public $prev;
}

class LinkedList {
  public $head;

  public function __construct(){
    $this->head = null;
  }
  
  //Add new element at the end of the list
  public function push_back($newElement) {
    $newNode = new Node();
    $newNode->data = $newElement;
    $newNode->next = null; 
    $newNode->prev = null;
    if($this->head == null) {
      $this->head = $newNode;
      $newNode->next = $this->head;
    } else {
      $temp = new Node();
      $temp = $this->head;
      while($temp->next !== $this->head) {
        $temp = $temp->next;
      }
      $temp->next = $newNode;
      $newNode->next = $this->head;
      $newNode->prev = $temp;
      $this->head->prev = $newNode;
    }    
  }

  //Delete last node by key
  public function pop_last($key) {       
    if($this->head != null) {
      $temp = new Node();
      $previousToLast = null;
      $lastNode = null;
      
      if($this->head->data == $key) 
        $lastNode = $this->head;
      
      $temp = $this->head;
      while($temp->next != $this->head) {
        if($temp->next->data == $key) {
          $previousToLast = $temp;
          $lastNode = $temp->next;
        }
        $temp = $temp->next;
      }
   
      if($lastNode != null) {
        if($lastNode == $this->head) {
          if($this->head->next == $this->head)
            $this->head = null;
          else {
            $this->head->prev->next = $this->head->next;
            $this->head = $this->head->next;
          }
          $lastNode = null;
        } else {
          $previousToLast->next = $lastNode->next;
          $previousToLast->next->prev = $previousToLast;
          $lastNode = null;
        }
      }
    }
  } 

  //display the content of the list
  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "The list contains: ";
      while(true) {
        echo $temp->data." ";
        $temp = $temp->next;
        if($temp == $this->head)
          break;        
      }
      echo "\n";
    } else {
      echo "The list is empty.\n";
    }
  }    
};

// test the code  
$MyList = new 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
AlphaCodingSkills
AlphaCodingSkills Android App
Facebook Page Twitter Page LinkedIn Page
Learning Tutorials
Learning Tutorials
Useful Links
Python Libraries
About Us  |  Privacy Policy  |  Contact Us
AlphaCodingSkills is a online learning portal that provides tutorials on Python, Java, C++, C, C#, PHP, R, Ruby, Rust, Scala, Swift, Perl, SQL, Data Structures and Algorithms. Tutorials, examples, references and content of the website are reviewed and simplified continuously to improve comprehensibility and eliminate any possible error. We use cookies to ensure best browsing experience on our website. While using this website, you acknowledge to have read and accepted our cookie and privacy policy.