Deleting a Node from a Circular Linked List in C

Back to: Data Structures and Algorithms Tutorials

Deleting a Node from a Circular Linked List in C Language

In this article, I am going to discuss Deleting a Node from a Circular Linked List in C Language with Examples. Please read our previous article, where we discussed Inserting a Node in a Circular Linked List in C Language with Examples. At the end of this article, you will understand how to delete a node in a Circular Linked List with algorithms and examples using C Language.

Deleting From Circular Linked List using C Language:

There are two cases for deletion just similar to a linear linked list.

1. Deleting Head Node in Circular Linked List.
2. Deleting a Node from a Given Position in a Circular Linked List.

If we delete the head node or the first node then we have to make another node as a head node in the circular linked list. So we will move head. We can select any node as a head node because it is a circular linked list. So we will be selecting just the next node as a head node.

The next method is deleting a node from the given position. We can delete any node i.e. 1^st, 2^nd, or 5^th node, or delete a node from any given position. This procedure is the same as deleting from the linear linked list. So, first, let us look at the second method.

Deleting A Node from the Given Position using C Language:

Let us delete a node from the 4^th index of the linked list.

So we want to delete the ‘3’ node. If we want to delete the 4^th node then we have to manipulate the node before the 4^th node i.e. 3^rd node. And make the 3^rd node point on the 5^th node. The only we can delete is the 4^th node. To access the 3^rd and 4^th nodes, we need a pointer on the 4^th node as well as on the 3^rd node (tail pointer). One pointer will be moving and the second pointer will be following the pointer. So we can bring two pointers from the beginning of the linked list or we can bring a pointer to 3^rd node and take one more pointer on the next node. So two options are there.

Now we will bring just one pointer from the head to 3^rd node then we take one more pointer on the next node. So we will be moving just one pointer. Let us take a pointer ‘p’ on the head node,

We want to delete the 4^th node, so we should bring p on the 3^rd node.

We have moved just 2 steps. 4^th nodes means 2 steps, 5^th nodes means 3 steps. So for deleting any node we have to move n – 2 steps. So the pseudo-code for this step is,

p = Head;
for (i = 0; i < pos-2; i++){
        p = p->next;
}

Now we need a pointer on the 4^th node also. So take another pointer ‘q’ and assign it to p->next,

q = p->next;

Here, q is pointing to p’s next node. Now, what changes do we have to make? P’s next should point on q’s next.

Now both p’s next and q’s next pointing on the 5^th node. Now we can easily delete the 4^th node because it is not the part of linked list. No node is pointing to the 4^th node. We will take out the value of the 4^th node and then delete the node.

int x = q->data;
delete q;

So we have deleted the 4^th node from the linked list. This procedure is the same as deleting from the linear linked list. The pseudo-code for this procedure is given below,

p = Head;
for (i = 0; i < pos-2; i++){
       p = p->next;
}
q = p->next;
p->next = q->next;
int x = q->data;
delete q;

Now let us see deleting the head node.

Deleting Head Node from a Circular Linked List using C Language:

If we are deleting the head node, we can make the next node as the head node but the last node should point to the new head node. So we have to do this modification to the new head node.

Now for deleting the head node, we should take a pointer p on the head node and move the p pointer until it reaches the last node as per the above head node,

Now we have to make p’s next to point on the head’s next node.

Here links have changed and now we have to make p’s next as Head. For that, first, we have to delete the head node,

Here, we have deleted the head’s node and made the p’s next as the head. So these are the steps for deleting the head node from the circular linked list. The pseudo-code for this procedure is given as,

p = Head;
while(p->next != Head)
         p = p->next;
p->next = Head->next;
x = Head->data;
delete Head;
Head = p->next;

Time Complexity:

The time taken for deleting the head node is n because we have to take p to the last node of the linked list. And the time taken for deleting any given node, the minimum is constant, and the maximum is n. If we are deleting 2^nd node then the time will be constant otherwise it will be n. Now let us look at the complete program.

Example to understand the deletion process in Circular Linked List using C Language:

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int data;
    struct Node * next;
}* Head;

void create(int A[], int n) {
    int i;
    struct Node * t, * last;
    Head = (struct Node * ) malloc(sizeof(struct Node));
    Head -> data = A[0];
    Head -> next = Head;
    last = Head;

    for (i = 1; i < n; i++) {
        t = (struct Node * ) malloc(sizeof(struct Node));
        t -> data = A[i];
        t -> next = last -> next;
        last -> next = t;
        last = t;
    }
}

void Display(struct Node * h) {
    do {
        printf("%d ", h -> data);
        h = h -> next;
    } while (h != Head);
    
    printf("\n");
}

void RDisplay(struct Node * h) {
    static int flag = 0;
    
    if (h != Head || flag == 0) {
        flag = 1;
        printf("%d ", h -> data);
        RDisplay(h -> next);
    }
    
    flag = 0;
}

int Length(struct Node * p) {
    int len = 0;
    do {
        len++;
        p = p -> next;

    } while (p != Head);
    
    return len;
}

void Insert(struct Node * p, int index, int x) {
    struct Node * t;
    int i;
    
    if (index < 0 || index > Length(p))
        return;

    if (index == 0) {
        t = (struct Node * ) malloc(sizeof(struct Node));
        t -> data = x;
        if (Head == NULL) {
            Head = t;
            Head -> next = Head;
        } else {
            while (p -> next != Head) p = p -> next;
            p -> next = t;
            t -> next = Head;
            Head = t;
        }

    } else {
        for (i = 0; i < index - 1; i++) p = p -> next;
        t = (struct Node * ) malloc(sizeof(struct Node));
        t -> data = x;
        t -> next = p -> next;
        p -> next = t;
    }
}

int Delete(struct Node * p, int index) {
    struct Node * q;
    int i, x;

    if (index < 0 || index > Length(Head))
        return -1;
    if (index == 1) {
        while (p -> next != Head) p = p -> next;
        x = Head -> data;
        if (Head == p) {
            free(Head);
            Head = NULL;
        } else {
            p -> next = Head -> next;
            free(Head);
            Head = p -> next;
        }
    } else {
        for (i = 0; i < index - 2; i++)
            p = p -> next;
        q = p -> next;
        p -> next = q -> next;
        x = q -> data;
        free(q);
    }
    return x;
}

int main() {
    int A[] = {9, 7, 4, 3, 2};
    create(A, 5);
    
    Display(Head);
    Delete(Head, 1);
    Display(Head);
    Delete(Head, 2);
    Display(Head);
    
    return 0;
}

Output:

In the next article, I am going to discuss Doubly Linked List in C Language with Examples. Here, in this article, I try to explain Deleting a Node in a Circular Linked List in C Language with Examples. I hope you enjoy this How to Delete a Node in a Circular Linked List with Algorithm and Examples article.