We have already discussed about 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 cicular 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->2[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 curr to next node, everytime 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 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 = temp -> next and delete curr.
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 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 data next == head] { cout 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 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[" "]; } /* 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[" 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 */ 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. 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[" "]; } /* 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[" 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; 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 program to test above functions */ 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 |