Deletion from a Circular Linked List
We have already discussed circular linked list and traversal in a circular linked list in the below articles:
Introduction to circular linked list
Traversal in a circular linked list
In this article, we will learn about deleting a node from a circular linked list. Consider the linked list as shown below:
We will be given a node and our task is to delete that node from the circular linked list.
Examples:
Input : 2->5->7->8->10->(head node) data = 5 Output : 2->7->8->10->(head node) Input : 2->5->7->8->10->(head node) 7 Output : 2->5->8->10->(head node)Algorithm
Case 1: List is empty.
- If the list is empty we will simply return.
Case 2:List is not empty
- If the list is not empty then we define two pointers curr and prev and initialize the pointer curr with the head node.
- Traverse the list using curr to find the node to be deleted and before moving to curr to the next node, every time set prev = curr.
- If the node is found, check if it is the only node in the list. If yes, set head = NULL and free(curr).
- If the list has more than one node, check if it is the first node of the list. Condition to check this( curr == head). If yes, then move prev until it reaches the last node. After prev reaches the last node, set head = head -> next and prev -> next = head. Delete curr.
- If curr is not the first node, we check if it is the last node in the list. Condition to check this is (curr -> next == head).
- If curr is the last node. Set prev -> next = head and delete the node curr by free(curr).
- If the node to be deleted is neither the first node nor the last node, then set prev -> next = curr -> next and delete curr.
Remove last node of the linked list
Given a linked list, the task is to remove the last node of the linked list and update the head pointer of the linked list.
Examples:
Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL Output: 1 -> 2 -> 3 -> 4 -> NULL Explanation: The last node of the linked list is 5, so 5 is deleted. Input: 2 -> 4 -> 6 -> 8 -> 33 -> 67 -> NULL Output: 2 -> 4 -> 6 -> 8 -> 33 -> NULL Explanation: The last node of the linked list is 67, so 67 is deleted.Approach: To delete the last node of a linked list, find the second last node and make the next pointer of that node null.
Algorithm:
1. If the first node is null or there is only one node, then they return null.
if headNode == null then return null if headNode.nextNode == null then free head and return null2. Create an extra space secondLast, and traverse the linked list till the second last node.
while secondLast.nextNode.nextNode != null secondLast = secondLast.nextNode3. delete the last node, i.e. the next node of the second last node delete(secondLast.nextNode), and set the value of the next second-last node to null.
Implementation:
|
// CPP program to remove last node of
// linked list.
#include <iostream>
using namespace std;
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* Function to remove the last node
of the linked list */
Node* removeLastNode(struct Node* head)
{
if (head == NULL)
return NULL;
if (head->next == NULL) {
delete head;
return NULL;
}
// Find the second last node
Node* second_last = head;
while (second_last->next->next != NULL)
second_last = second_last->next;
// Delete last node
delete (second_last->next);
// Change next of second last
second_last->next = NULL;
return head;
}
// Function to push node at head
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// Driver code
int main()
{
/* Start with the empty list */
Node* head = NULL;
/* Use push() function to construct
the below list 8 -> 23 -> 11 -> 29 -> 12 */
push(&head, 12);
push(&head, 29);
push(&head, 11);
push(&head, 23);
push(&head, 8);
head = removeLastNode(head);
for (Node* temp = head; temp != NULL; temp = temp->next)
cout << temp->data << " ";
return 0;
}
|
|
// Java program to remove last node of
// linked list.
class GFG {
// Link list node /
static class Node {
int data;
Node next;
};
// Function to remove the last node
// of the linked list /
static Node removeLastNode(Node head)
{
if (head == null)
return null;
if (head.next == null) {
return null;
}
// Find the second last node
Node second_last = head;
while (second_last.next.next != null)
second_last = second_last.next;
// Change next of second last
second_last.next = null;
return head;
}
// Function to push node at head
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
// Driver code
public static void main(String args[])
{
// Start with the empty list /
Node head = null;
// Use push() function to con
// the below list 8 . 23 . 11 . 29 . 12 /
head = push(head, 12);
head = push(head, 29);
head = push(head, 11);
head = push(head, 23);
head = push(head, 8);
head = removeLastNode(head);
for (Node temp = head; temp != null; temp = temp.next)
System.out.print(temp.data + " ");
}
}
// This code is contributed by Arnab Kundu
|
|
# Python3 program to remove the last node of
# linked list.
import sys
import math
# Link list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to push node at head
def push(head, data):
if not head:
return Node(data)
temp = Node(data)
temp.next = head
head = temp
return head
# Function to remove the last node
# of the linked list
def removeLastNode(head):
if head == None:
return None
if head.next == None:
head = None
return None
second_last = head
while(second_last.next.next):
second_last = second_last.next
second_last.next = None
return head
# Driver code
if __name__=='__main__':
# Start with the empty list
head = None
# Use push() function to con
# the below list 8 . 23 . 11 . 29 . 12
head = push(head, 12)
head = push(head, 29)
head = push(head, 11)
head = push(head, 23)
head = push(head, 8)
head = removeLastNode(head)
while(head):
print("{} ".format(head.data), end ="")
head = head.next
# This code is contributed by Vikash kumar 37
|
|
// C# program to remove last node of
// linked list.
using System;
class GFG {
// Link list node /
public class Node {
public int data;
public Node next;
};
// Function to remove the last node
// of the linked list /
static Node removeLastNode(Node head)
{
if (head == null)
return null;
if (head.next == null) {
return null;
}
// Find the second last node
Node second_last = head;
while (second_last.next.next != null)
second_last = second_last.next;
// Change next of second last
second_last.next = null;
return head;
}
// Function to push node at head
static Node push(Node head_ref, int new_data)
{
Node new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
// Driver code
public static void Main(String[] args)
{
// Start with the empty list /
Node head = null;
// Use push() function to con
// the below list 8 . 23 . 11 . 29 . 12 /
head = push(head, 12);
head = push(head, 29);
head = push(head, 11);
head = push(head, 23);
head = push(head, 8);
head = removeLastNode(head);
for (Node temp = head; temp != null; temp = temp.next)
Console.Write(temp.data + " ");
}
}
/* This code contributed by PrinciRaj1992 */
|
|
<script>
// javascript program to remove last node of
// linked list. // Link list node /
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Function to remove the last node
// of the linked list /
function removeLastNode(head)
{
if (head == null)
return null;
if (head.next == null) {
return null;
}
// Find the second last node
var second_last = head;
while (second_last.next.next != null)
second_last = second_last.next;
// Change next of second last
second_last.next = null;
return head;
}
// Function to push node at head
function push(head_ref , new_data)
{
var new_node = new Node();
new_node.data = new_data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
// Driver code
// Start with the empty list /
var head = null;
// Use push() function to con
// the below list 8 . 23 . 11 . 29 . 12 /
head = push(head, 12);
head = push(head, 29);
head = push(head, 11);
head = push(head, 23);
head = push(head, 8);
head = removeLastNode(head);
for (temp = head; temp != null; temp = temp.next)
document.write(temp.data + " ");
// This code contributed by Rajput-Ji
</script>
|
Complexity Analysis:
-
Time Complexity: O(n).
The algorithm involves traversal of the linked list till its end, so the time complexity required is O(n). -
Space Complexity: O(1).
No extra space is required, so the space complexity is constant.
Deletion in Circular singly linked list at the end
There are three scenarios of deleting a node in circular singly linked list at the end.
Scenario 1 (the list is empty)
If the list is empty then the condition head == NULL will become true, in this case, we just need to print underflow on the screen and make exit.
Scenario 2(the list contains single element)
If the list contains single node then, the condition head → next == head will become true. In this case, we need to delete the entire list and make the head pointer free. This will be done by using the following statements.
Scenario 3(the list contains more than one element)
If the list contains more than one element, then in order to delete the last element, we need to reach the last node. We also need to keep track of the second last node of the list. For this purpose, the two pointers ptr and preptr are defined. The following sequence of code is used for this purpose.
now, we need to make just one more pointer adjustment. We need to make the next pointer of preptr point to the next of ptr (i.e. head) and then make pointer ptr free.
Q. Program to delete a new node from the end of the circular linked list.
Explanation
In this program, we will create a circular linked list and delete a node from the end of the list. If the list is empty, it will display the message "List is empty". If the list is not empty, we will loop through the list till second last node is reached. We will make second last node as the new tail, and this new tail will point to head and delete the previous tail.
Circular linked list after deleting node from end
Here, in the above list, D is the last node which needs to be deleted. We will iterate through the list till C. Make C as new tail and C will point back to head A.
Algorithm
- Define a Node class which represents a node in the list. It has two properties data and next which will point to the next node.
- Define another class for creating the circular linked list and it has two nodes: head and tail. It has two methods: deleteEnd() and display() .
- deleteEnd() will delete the node from the end of the list:
- It first checks whether the head is null (empty list) then, it will return from the function as there is no node present in the list.
- If the list is not empty, it will check whether list has only one node.
- If the list has only one node, it will set both head and tail to null.
- If the list has more than one node then, iterate through the loop till current.next!= tail.
- Now, current will point to the node previous to tail. Make current as new tail and tail will point to head thus, deletes the node from last.
- display() will show all the nodes present in the list.
- Define a new node 'current' that will point to the head.
- Print current.data till current will points to head again.
- Current will point to the next node in the list in each iteration.
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
Complete program to demonstrate deletion in Circular Linked List:
C++
// C++ program to delete a given key from // linked list. #include <bits/stdc++.h> using namespace std; /* structure for a node */ class Node { public: int data; Node *next; }; /* Function to insert a node at the beginning of a Circular linked list */ void push(Node **head_ref,int data) { // Create a new node and make head as next // of it. Node *ptr1 =new Node(); ptr1->data = data; ptr1->next = *head_ref; /* If linked list is not NULL then set the next of last node */ if (*head_ref != NULL) { // Find the node before head and update // next of it. Node *temp = *head_ref; while (temp->next != *head_ref) temp = temp->next; temp->next = ptr1; } else ptr1->next = ptr1;/*For the first node */ *head_ref = ptr1; } /* Function to print nodes in a given circular linked list */ void printList(Node *head) { Node *temp = head; if (head != NULL) { do { cout << temp->data <<" "; temp = temp->next; } while (temp != head); } cout << endl; } /* Function to delete a given node from the list */ void deleteNode(Node *head,int key) { if (head == NULL) return; // Find the required node Node *curr = head, *prev; while (curr->data != key) { if (curr->next == head) { cout <<" Given node is not found" " in the list!!!"; break; } prev = curr; curr = curr -> next; } // Check if node is only node if (curr->next == head) { head = NULL; free(curr); return; } // If more than one node, check if // it is first node if (curr == head) { prev = head; while (prev -> next != head) prev = prev -> next; head = curr->next; prev->next = head; free(curr); } // check if node is last node else if (curr -> next == head) { prev->next = head; free(curr); } else { prev->next = curr->next; free(curr); } } /* Driver program to test above functions */ int main() { /* Initialize lists as empty */ Node *head = NULL; /* Created linked list will be 2->5->7->8->10 */ push(&head, 2); push(&head, 5); push(&head, 7); push(&head, 8); push(&head, 10); cout <<"List Before Deletion: "; printList(head); deleteNode(head, 7); cout <<"List After Deletion: "; printList(head); return 0; } // This is code is contributed by rathbhupendra |