Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
1.2.1.
Example 1
1.2.2.
Example 2
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Complexities
3.
Frequently Asked Questions
3.1.
In a circular linked list, what is deletion?
3.2.
Is removing a node from a circular linked list possible?
3.3.
What happens if an element in a linked list is removed?
3.4.
How many changes are needed to remove a node from the beginning?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Deletion in a Circular Linked List

Author Palak Mishra
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

The Circular Linked List is one of the most important data structures to grasp when preparing for Coding Interviews.

A circular linked list is one in which all nodes are connected in a circle, with the last node pointing back to the head node to complete the cycle's loop. No nodes are pointing to the NULL, indicating that no end node exists. 

We'll look at how to remove a specified node from a Circular Linked List in this article.

                                                

Problem Statement

We are given a circular linked list and a node, and our task is to delete the node with the given value X from the given Circular Linked List, i.e., the given node must not be present in the Circular Linked List after the deletion operation is completed. If no such key exists, the list will remain unaltered.

Also read - Merge sort in linked list

Sample Example

Example 1

Input : 1->3->7->5->9->4->(head node)
        data = 3

                                              

 

Output :1->7->5->9->4->(head node)

                                             

 

Example 2

Input : 1->3->5->7->9->4->(head node)
         data = 7

                                              

 

Output : 1->3->5->9->4->(head node)

                                            

Recommended Topic, Floyds Algorithm and Rabin Karp Algorithm

Approach

We are performing deletion operations in the following cases:

  • When the list is empty.
  • When the list is not empty.

Algorithm

For the deletion operation, the following scenarios may persist:

  • The List is currently empty.
    If the Circular list is empty, that is, the head is set to NULL, and the function will return NULL.
     
  • The node in question does not exist in the Circular Linked List.
    We will simply print that the Specified node that is not present in the list and returns the head node if we have scanned the list entirely and are unable to locate the given node to be deleted.
     
  • We've located the node

    So, in this scenario, we'll need to maintain track of the node and its predecessor, and we'll be able to do the following operations:
     
  1. If the list only includes one node, the head will be set to NULL and the head node will be returned.
    If there are more than two nodes in the list, we will do the following operations.
     
  2. To begin, set the curr pointer to the node we want to delete, and the prev refers to curr's preceding node.
     
  3. We'll now set the prev pointer to the next of the curr pointer and set the next of the curr pointer to NULL.
     
  4. Then, if the curr pointer is the head node, the head node must be updated with the next head node.
     
  5. Finally, the head representing the new Circular Linked List is returned.

 

                                                     

Implementation



#include <stdio.h>
#include <stdlib.h>
 
struct Node {
    int data;
    struct Node* next;
};
 
/* Insert a node at the start of a circular linked list with this function. */
void push(struct Node** head_ref, int data)
{
    struct Node* ptr1 = (struct Node*)malloc(sizeof(struct Node));
    ptr1->data = data;
    ptr1->next = *head_ref;
    if (*head_ref != NULL) {
     
        struct Node* temp = *head_ref;
        while (temp->next != *head_ref)
            temp = temp->next;
        temp->next = ptr1;
    }
    else
        ptr1->next = ptr1; /*For the initial node */
 
    *head_ref = ptr1;
}
 
/*Nodes in a circular linked list are printed using this function.  */
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");
}
 
/*Deletes a specified node from the list. */
void deleteNode(struct Node* head, int key)
{
    if (head == NULL)
        return;
 
    // Locate the necessary node.
    struct Node *curr = head, *prev;
    while (curr->data != key)
    {
        if (curr->next == head)
        {
            printf("\nGiven node is not found"
                   " in here!!!");
            break;
        }
 
        prev = curr;
        curr = curr->next;
    }
 
    // Check to see if the node is the only one.
    if (curr->next == head)
    {
        head = NULL;
        free(curr);
        return;
    }
 
    // If there are more than one node, see if it's the first one.
    if (curr == head)
    {
        prev = head;
        while (prev->next != head)
            prev = prev->next;
        head = curr->next;
        prev->next = head;
        free(curr);
    }
 
    //  if this one is last node
    else if (curr->next == head && curr == head)
    {
        prev->next = head;
        free(curr);
    }
    else
    {
        prev->next = curr->next;
        free(curr);
    }
}
 
/* Driver code for the main */
int main()
{
    /* Initi lists as empty */
    struct Node* head = NULL;
 
    /* Created linked list will be */
    push(&head, 9);
    push(&head, 3);
    push(&head, 7);
    push(&head, 5);
    push(&head, 6);
 
    printf("Before Deletion: ");
    printList(head);
 
    deleteNode(head, 7);
 
    printf("After Deletion: ");
    printList(head);
 
    return 0;
}
You can also try this code with Online C Compiler
Run Code

 

Output

Before Deletion: 6 5 7 3 9 
After Deletion: 6 5 3 9 

 

Complexities

  • Time complexity: O(N), where n is the size of the circular linked list. The time it takes to traverse the list is linear. As a result, the complexity of time is O. (n).
  • Auxiliary Space: O(1), The memory we consume is constant and independent of the data it is processing.

     

Frequently Asked Questions

In a circular linked list, what is deletion?

If the given circular linked list does not contain a node with value X, we must print that the given node is not present in the list and return the head node. If a node with the value X exists, it will be removed from the list, and the modified list will be returned.

Is removing a node from a circular linked list possible?

Singly Circular Linked List's first node is being deleted. Take current and previous pointers, and traverse the list with them. Maintain the current pointer pointing to the first node and move the pointer backward until it reaches the last node.

What happens if an element in a linked list is removed?

A move is used in conjunction with the delete command. The previous item's next element in the linked list now points to the element after the deleted one.

How many changes are needed to remove a node from the beginning?

The most straightforward operation is removing a node from the beginning list. The node pointers need to be tweaked a little. Because the initial node of the list will be erased, we need to make the head and point to the next head.

Conclusion

This article discussed how to delete the node with the value X from the given circular linked list, as stated in the problem statement. Also, after a node is deleted, how the linked list should retain its circular property. 

We hope that this article has helped you enhance your knowledge regarding the subject of deletion in a circular Linked List.

To study more about Linked Lists, refer to Applications Of Linked Lists.

After reading about the deletion in a circular link list, are you not feeling excited to read/explore more articles on this topic? Don't worry; Coding Ninjas has you covered. You can learn more about Why is Quick Sort preferred for Arrays and Merge Sort for Linked Lists?   Application of Linked List Data Structure, and Linked List remove() Method in Java  Also see time complexity and Complexity Analysis.

You can also practice some relevant problems at Coding Ninjas Studio such as:

  1. Deletion of a linked list
  2. Unrolled linked list
  3. Implementing a Linked List in Java Using Class
  4. LinkedList descendingIterator in Java
     

You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc., you must look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

 

Live masterclass