Data Structures - Circular Singly Linked List Other Related Topics

Circular Singly Linked List - Delete last node by key



In this method, last node in the circular singly 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 = head->next;
        free(lastNode);
      } else {
        previousToLast->next = lastNode->next;
        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 = (*head_ref)->next;
        free(lastNode);
      } else {
        previousToLast->next = lastNode->next;
        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 = self.head.next
        lastNode = None
      else:
        previousToLast.next = lastNode.next
        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 = head.next;
        lastNode = null;
      } else {
        previousToLast.next = lastNode.next;
        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 = head.next;
        lastNode = null;
      } else {
        previousToLast.next = lastNode.next;
        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 = $this->head->next;
        $lastNode = null;
      } else {
        $previousToLast->next = $lastNode->next;
        $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 singly linked list.

#include <iostream>
using namespace std;

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

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; 
      if(head == NULL) {
        head = newNode;
        newNode->next = head;
      } else {
        Node* temp = head;
        while(temp->next != head)
          temp = temp->next;
        temp->next = newNode;
        newNode->next = head;
      }    
    }

    //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 = head->next;
            free(lastNode);
          } else {
            previousToLast->next = lastNode->next;
            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 in 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;
};

//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;
  if(*head_ref == NULL) {
    *head_ref = newNode;
     newNode->next = *head_ref;
  } else {
    temp = *head_ref;
    while(temp->next != *head_ref) {
      temp = temp->next;
    }    
    temp->next = newNode;
    newNode->next = *head_ref;
  }
}

//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 = (*head_ref)->next;
        free(lastNode);
      } else {
        previousToLast->next = lastNode->next;
        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 in 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

#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
      return
    else:
      temp = self.head
      while(temp.next != self.head):
        temp = temp.next
      temp.next = newNode
      newNode.next = self.head

  #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 = self.head.next
          lastNode = None
        else:
          previousToLast.next = lastNode.next
          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 in 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;
};

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; 
    if(head == null) {
      head = newNode;
      newNode.next = head;
    } else {
      Node temp = new Node();
      temp = head;
      while(temp.next != head)
        temp = temp.next;
      temp.next = newNode;
      newNode.next = head;
    }    
  }

  //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 = head.next;
          lastNode = null;
        } else {
          previousToLast.next = lastNode.next;
          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 in 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;
};

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; 
    if(head == null) {
      head = newNode;
      newNode.next = head;
    } else {
      Node temp = new Node();
      temp = head;
      while(temp.next != head)
        temp = temp.next;
      temp.next = newNode;
      newNode.next = head;
    }    
  }

  //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 = head.next;
          lastNode = null;
        } else {
          previousToLast.next = lastNode.next;
          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 in 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;
}

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; 
    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;
    }    
  }

  //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 = $this->head->next;
          $lastNode = null;
        } else {
          $previousToLast->next = $lastNode->next;
          $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 in 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