Tutorialspoint.dev

Deletion from a Circular Linked List

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:
cll_inserted

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.


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

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(" ");
}
  
/* 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

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter