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.
Complete program to demonstrate deletion in Circular Linked List:
C++14
// 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 linked list is empty if (*head == NULL) return ; // If the list contains only a single node if ((*head)->data==key && (*head)->next==*head) { free (*head); *head=NULL; return ; } Node *last=*head,*d; // If head is to be deleted if ((*head)->data==key) { // Find the last node of the list while (last->next!=*head) last=last->next; // Point last node to the next of head i.e. // the second node of the list last->next=(*head)->next; free (*head); *head=last->next; return ; } // Either the node to be deleted is not found // or the end of list is not reached while (last->next!=*head&&last->next->data!=key) { last=last->next; } // If node to be deleted was found if (last->next->data==key) { d=last->next; last->next=d->next; free (d); } else cout<< "no such keyfound" ; } /* Driver code */ 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 |
C
// C program to delete a given key from // linked list. #include <stdio.h> #include <stdlib.h> /* structure for a node */ struct Node { int data; struct Node* next; }; /* Function to insert a node at the beginning of a Circular linked list */ void push( struct Node** head_ref, int data) { // Create a new node and make head as next // of it. struct Node* ptr1 = ( struct Node*) malloc ( sizeof ( struct 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. struct 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( struct Node* head) { struct Node* temp = head; if (head != NULL) { do { printf ( "%d " , temp->data); temp = temp->next; } while (temp != head); } printf ( "\n" ); } /* Function to delete a given node from the list */ void deleteNode( struct Node* head, int key) { if (head == NULL) return ; // Find the required node struct Node *curr = head, *prev; while (curr->data != key) { if (curr->next == head) { printf ( "\nGiven 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 && curr == head) { prev->next = head; free (curr); } else { prev->next = curr->next; free (curr); } } /* Driver code */ int main() { /* Initialize lists as empty */ struct 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); printf ( "List Before Deletion: " ); printList(head); deleteNode(head, 7); printf ( "List After Deletion: " ); printList(head); return 0; } |
Java
// Java program to delete a given key from // linked list. import java.util.*; import java.io.*; public class GFG { /* ure for a node */ static class Node { int data; Node next; }; /* Function to insert a node at the beginning of a Circular linked list */ static Node 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; return head_ref; } /* Function to print nodes in a given circular linked list */ static void printList(Node head) { Node temp = head; if (head != null ) { do { System.out.printf( "%d " , temp.data); temp = temp.next; } while (temp != head); } System.out.printf( "\n" ); } /* Function to delete a given node from the list */ static Node deleteNode(Node head, int key) { if (head == null ) return null ; // Find the required node Node curr = head, prev = new Node(); while (curr.data != key) { if (curr.next == head) { System.out.printf( "\nGiven node is not found" + " in the list!!!" ); break ; } prev = curr; curr = curr.next; } // Check if node is only node if (curr == head && curr.next == head) { head = null ; return head; } // 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; } // check if node is last node else if (curr.next == head) { prev.next = head; } else { prev.next = curr.next; } return head; } /* Driver code */ public static void main(String args[]) { /* Initialize lists as empty */ Node head = null ; /* Created linked list will be 2.5.7.8.10 */ head = push(head, 2 ); head = push(head, 5 ); head = push(head, 7 ); head = push(head, 8 ); head = push(head, 10 ); System.out.printf( "List Before Deletion: " ); printList(head); head = deleteNode(head, 7 ); System.out.printf( "List After Deletion: " ); printList(head); } } // This code is contributed by Arnab Kundu // This code is updated by Susobhan Akhuli |
Python
# Python program to delete a given key from # linked list. # Node of a doubly linked list class Node: def __init__( self , next = None , data = None ): self . next = next self .data = data # Function to insert a node at the beginning of # a Circular linked list def push(head_ref, data): # Create a new node and make head as next # of it. ptr1 = Node() ptr1.data = data ptr1. next = head_ref # If linked list is not None then set the # next of last node if (head_ref ! = None ) : # Find the node before head and update # next of it. 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 return head_ref # Function to print nodes in a given # circular linked list def printList( head): temp = head if (head ! = None ) : while ( True ) : print ( temp.data, end = " " ) temp = temp. next if (temp = = head): break print () # Function to delete a given node from the list def deleteNode( head, key) : # If linked list is empty if (head = = None ): return # If the list contains only a single node if ((head).data = = key and (head). next = = head): head = None last = head d = None # If head is to be deleted if ((head).data = = key) : # Find the last node of the list while (last. next ! = head): last = last. next # Point last node to the next of head i.e. # the second node of the list last. next = (head). next head = last. next # Either the node to be deleted is not found # or the end of list is not reached while (last. next ! = head and last. next .data ! = key) : last = last. next # If node to be deleted was found if (last. next .data = = key) : d = last. next last. next = d. next else : print ( "no such keyfound" ) return head # Driver code # Initialize lists as empty head = None # Created linked list will be 2.5.7.8.10 head = push(head, 2 ) head = push(head, 5 ) head = push(head, 7 ) head = push(head, 8 ) head = push(head, 10 ) print ( "List Before Deletion: " ) printList(head) head = deleteNode(head, 7 ) print ( "List After Deletion: " ) printList(head) # This code is contributed by Arnab Kundu |
C#
// C# program to delete a given key from // linked list. using System; class GFG { /* structure for a node */ public class Node { public int data; public Node next; }; /* Function to insert a node at the beginning of a Circular linked list */ static Node 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; return head_ref; } /* Function to print nodes in a given circular linked list */ static void printList(Node head) { Node temp = head; if (head != null ) { do { Console.Write( "{0} " , temp.data); temp = temp.next; } while (temp != head); } Console.Write( "\n" ); } /* Function to delete a given node from the list */ static Node deleteNode(Node head, int key) { if (head == null ) return null ; // Find the required node Node curr = head, prev = new Node(); while (curr.data != key) { if (curr.next == head) { Console.Write( "\nGiven node is not found" + " in the list!!!" ); break ; } prev = curr; curr = curr.next; } // Check if node is only node if (curr.next == head && curr == head) { head = null ; return head; } // 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; } // check if node is last node else if (curr.next == head) { prev.next = head; } else { prev.next = curr.next; } return head; } /* Driver code */ public static void Main(String[] args) { /* Initialize lists as empty */ Node head = null ; /* Created linked list will be 2.5.7.8.10 */ head = push(head, 2); head = push(head, 5); head = push(head, 7); head = push(head, 8); head = push(head, 10); Console.Write( "List Before Deletion: " ); printList(head); head = deleteNode(head, 7); Console.Write( "List After Deletion: " ); printList(head); } } // This code has been contributed by 29AjayKumar |
Javascript
<script> // javascript program to delete a given key from // linked list. /* ure for a node */ class Node { constructor() { this .data = 0; this .next = null ; } } /* * Function to insert a node at the beginning of a Circular linked list */ function push(head_ref , data) { // Create a new node and make head as next // of it. var 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. var 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; return head_ref; } /* * Function to print nodes in a given circular linked list */ function printList(head) { var temp = head; if (head != null ) { do { document.write( temp.data+ " " ); temp = temp.next; } while (temp != head); } document.write( "<br/>" ); } /* Function to delete a given node from the list */ function deleteNode(head , key) { if (head == null ) return null ; // Find the required node var curr = head, prev = new Node(); while (curr.data != key) { if (curr.next == head) { document.write( "<br/>Given node is not found" + " in the list!!!" ); break ; } prev = curr; curr = curr.next; } // Check if node is only node if (curr == head && curr.next == head) { head = null ; return head; } // 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; } // check if node is last node else if (curr.next == head) { prev.next = head; } else { prev.next = curr.next; } return head; } /* Driver code */ /* Initialize lists as empty */ var head = null ; /* Created linked list will be 2.5.7.8.10 */ head = push(head, 2); head = push(head, 5); head = push(head, 7); head = push(head, 8); head = push(head, 10); document.write( "List Before Deletion: " ); printList(head); head = deleteNode(head, 7); document.write( "List After Deletion: " ); printList(head); // This code contributed by umadevi9616 </script> |
Output
List Before Deletion: 10 8 7 5 2 List After Deletion: 10 8 5 2
Time Complexity: O(n), Worst case occurs when the element to be deleted is the last element and we need to move through the whole list.
Auxiliary Space: O(1), As constant extra space is used.
Contact Us