Deletion in Circular Linked List

Last Updated on July 31, 2023 by Mayank Dham

A circular linked list is a variation of the traditional linked list where the last node points back to the first node, creating a circular structure. Deletion in a circular linked list involves removing a node while maintaining the circular arrangement. This operation requires careful manipulation of pointers to ensure the list remains connected and no memory leaks occur.

In this article, we will delve into the algorithm for deleting a node in a circular linked list. We will explore various scenarios, such as deleting the first, last, or middle node, and address the necessary steps to adjust the pointers correctly. Additionally, we will discuss the time complexity and space complexity of the deletion algorithm to analyze its efficiency.

What is Circular Linked List?

A circular linked list is a type of list where every node is linked to form a cycle. This means that the last node points to the first node, forming a complete loop in the list. Unlike a regular linked list, no node points to NULL, indicating the end of the list.

The following image illustrates the difference between a normal linked list and a circular linked list.

Deletion in Circular Linked List

We are given a circular linked list and a node, and our task is to delete the node with a given value X from the given circular linked List i.e, After performing the deletion in circular linked list, the given node should not be present in the Circular Linked List.

Note: We are assuming that the given linked list does not contain duplicate nodes (nodes having the same values).

How To Perform Deletion in Circular Linked List?

Let’s try to understand the problem statement with the help of examples.

Example 1:
Let’s say if the given circular linked list is:

and X = 14.

• So now, according to the problem statement, we need to delete the node with value X from the given circular linked list. also linked list should maintain its property of being circular after the deletion of the node.
• If the node with value X is not present in the given circular linked list, then we will have to simply print the Given node is not present in the list and return the head node.
• If a node with value X is present, we will delete it from the list and return the modified list.
• In this example, the node with value X = 14 is present in the list, so we delete it and return the modified list.

Note: Also, you must make sure that the modified list should be a circular linked list after deletion i.e, all the nodes are still connected forming a cycle.

Example 2:
If the given circular linked list is:

and X = 7.

• So we can see that X = 7 is not present in the given linked list, so we will print Given node is not present in the list.

Now I think from the above examples, the problem is clear. So let’s see how we can approach it.

Before moving to the approach section, try to think about how you can approach this problem.

• If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach for Deletion In Circular Linked List

Our approach for performing the deletion on circular linked list will be simple and will have the following steps.

• The idea is to traverse the given circular linked list and find the position of the node which we have to delete.

• To do a traversal of the given circular linked list, we will create a new Node pointer curr, which will start from the head and traverse through each node in the list until it reaches the head again.

  • If we reach head again without finding the key (the value of the node which we have to delete) then we will simply print “Given node is not present in the list” and return the original list.
  • While traversing, we will also keep track of the previously visited node using a node pointer prev. The use of the prev pointer is that when we find the node we have to delete i.e, (curr == key), we can simply make prev.next point to the next of the curr node (prev.next = curr.next).

  

• Thus, breaking the bond between the prev and curr. But one thing to notice here is that curr.next will still point to the next node in the list. So to break this bond we make curr.next point to NULL.

• In this way, we will successfully delete the node we were asked to delete in the problem.

Now let’s move to the algorithm section.

Algorithm For Deletion In Circular Linked List

The algorithm for deletion in circular linked list for the three different cases is given below.

• The List is empty.
  • If the given list is empty, i.e., the head is assigned as NULL, then we will return NULL from the function.
• The given node is not present in the Circular Linked List.
  • If we have completely traversed the list and are unable to find the given node to be deleted, we will simply print Given node is not present in the list and return the head node.
• We have found the node.
  • So, in this case, we need to keep track of the node and its previous node and can perform the suitable operations from the following:
    • If the list has only one node, then we will assign the head as NULL and return the head node.
    • If the list has more than or equal to two nodes, we will perform the below operations:
      • First, make curr pointer point to the node which we want to delete and prev pointer point to the previous node of curr.
      • Now, we will make the prev pointer point to the next of curr pointer and assign the next of curr pointer as NULL.
      • Then, if the curr pointer is the head node, we need to update the head node with the next of the head node.
      • At last, we return the head representing the new Circular Linked List.

For the clear understanding, let’s move to the dry run for the deletion in circular linked list.

Dry Run for Deletion In Circular Linked List

The dry run for performing the deletion in circular linked list is given below for a better understanding.

Code Implementation of Deletion in Circular Linked List

The code for the deletion in circular linked list in C, C++, and Python are given below.

#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)
{
    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 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;
}

#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;
}

class Node:
    def __init__(self, next = None, data = None):
        self.next = next
        self.data = data

# This function is used to insert a new node at the beginning of the circular linked list.
def push(head_ref, data):

    ptr1 = Node()
    ptr1.data = data
    ptr1.next = head_ref

    if (head_ref != None) :
        
        temp = head_ref
        while (temp.next != head_ref):
            temp = temp.next
        temp.next = ptr1
    
    else:
        ptr1.next = ptr1

    head_ref = ptr1
    return head_ref


# This is the main function which will delete the node which have value equal to key
def deleteNode( head, key) :
    
    if (head == None):
        return
    
    if((head).data == key and (head).next == head):
    
        head = None
    
    last = head
    d = None
    
    if((head).data == key) :
    
        while(last.next != head):
            last = last.next
    
        last.next = (head).next
        head = last.next
    
    while(last.next != head and last.next.data != key) :
        last = last.next

    if(last.next.data == key) :
        d = last.next
        last.next = d.next
    
    else:
        print("no such keyfound")
    
    return head

# Once we have successfully deleted the specified node, this function will be used to print the modified list.
def printList( head):

    temp = head
    if (head != None) :
        while(True) :
            print( temp.data, end = " ")
            temp = temp.next
            if (temp == head):
                break
    print()



head = None

head = push(head, 5)
head = push(head, 8)
head = push(head, 3)
head = push(head, 4)
head = push(head, 7)
head = push(head, 6)
head = push(head, 9)

print("List Before Deletion: ")
printList(head)

head = deleteNode(head, 7)

print( "List After Deletion: ")
printList(head)

Output

List Before Deletion: 9 6 7 4 3 8 5
List After Deletion: 9 6 4 3 8 5

Time Complexity of Deletion in Circular Linked List: O(n) is the time complexity for deletion in circular linked list, where n is the number of nodes in the circular linked list. Traversing the list takes a linear amount of time. Hence, the time complexity is O(n).

Space Complexity of Deletion in Circular Linked List: O(1) is the time complexity for deletion in circular linked list, since we are not using any extra space for deletion in circular linked list.

Conclusion
In this article, we provided a detailed explanation of how to perform deletion in circular linked list. As Linked List is a crucial topic for placements and interviews, understanding the deletion in circular linked list enhances one’s knowledge about data structures and their benefits. This is a basic problem and is good for strengthening your concepts in LinkedList and if you want to practice more such problems, you can check out Prepbytes (Linked List).

Frequently Asked Questions(FAQs)

Here are some frequently asked questions on deletion in circular linked list.

Ques 1. How is a Circular Linked List different from a regular Linked List?
Ans. A Circular Linked List is different from a regular Linked List in that the last node points to the first node to form a cycle, whereas in a regular Linked List, the last node points to NULL to indicate the end of the list.

Ques 2. What is the advantage of using a Circular Linked List?
Ans. The advantage of using a Circular Linked List is that it allows for efficient traversal of the list since there is no need to check for NULL when traversing the list.

Ques 3. Can a Circular Linked List have a NULL value as a node?
Ans. No, a Circular Linked List cannot have a NULL value as a node since the last node points to the first node to form a cycle.

Ques 4. What is the worst-case time complexity of searching for a node in a Circular Linked List?
Ans. The worst-case time complexity of searching for a node in a Circular Linked List is O(N).