# Deletion from a Circular Linked List

Traversal in a circular linked list

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

7
```

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 << 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 `

## C

 `// C program to delete a given key from ` `// linked list. ` `#include ` `#include ` ` `  `/* 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``(````" "````); ` `} ` ` `  `/* 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 `

Output:

```List Before Deletion: 10 8 7 5 2
List After Deletion: 10 8 5 2
```