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