Circular Linked List Insertion and Deletion Program in C

June 14, 2022

C Program for Circular Linked List Insertion and Deletion

On this page, we will look at the following –

Insertion/Deletion at Start
Insertion/Deletion at the End
Insertion/Deletion at a Position

What is a Circular Linked List

A Circular Linked List is almost very similar to a singly linked list. With just one difference that the last node of the circular linked list is connected to the first node in the list.

While in a singly linked list the last node is connected to a null node.

Following are some terminologies of a Circular Linked List –

Head node
Node
Next Pointer
Data

Some variations also support a tail node that represents the last node in a circular linked List

Possible Positions to insert / delete

In the programs we will look at we will do insertions/deletions at the following positions –

At Front
At End
Insertion After nth node / Deletion of nth node

Program to Insert in a Circular Linked List

This program covers insertion at

At front
At End
After nth node

Run

#include<stdio.h>
#include<stdlib.h>
// structure for Circular Linked List
struct Node
{
   int data;
   struct Node *next;
};

int calcSize(struct Node* head);

void insertFront(struct Node** head, int data)
{
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    
    // if its the first node being entered
    if(*head == NULL){
        *head = newNode; // assigning itself as head
        (*head)->next = *head; // assigning itself as next node
        return;
    }
    
    // if CLL already as >=1 node
    struct Node* curr = *head;
    
    // traverse till last node in CLL
    while(curr->next != *head){
        curr = curr->next;
    }
    
    curr->next = newNode; // last node's next as this new node
    newNode->next = *head; // new node's next as current head node
    *head = newNode; // changing head node to this new node
    
    // previous head node becomes 2nd node
}

void insertEnd(struct Node** head, int data){
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    
    // if its the first node being entered
    if(*head == NULL){
        *head = newNode;
        (*head)->next = *head;
        return;
    }
    
    // if CLL already as >=1 node
    struct Node* curr = *head;
    
    // traverse till last node in CLL
    while(curr->next != *head){
        curr = curr->next;
    }
    
    // assign CLL's current last node's next as this new node
    curr->next = newNode;
    
    // assign this new node's next as current head of CLL
    newNode->next = *head;
}

void insertAfterPosition(int pos, int data, struct Node** head){
    int size = calcSize(*head);
    
    if(pos < 0 || size < pos) { 
        printf("Can't insert, %d is not a valid position\n",pos); 
    } 
    else if(pos == 0) 
        insertFront(head, data); 
    else 
    { 
        struct Node* newNode = (struct Node*) malloc(sizeof(struct Node)); 
        newNode->data = data;
        
        struct Node* temp = *head;
        
        // traverse till the node after which you need to
        // insert this new node
        while(--pos)
            temp = temp->next;
        
        // since we need to insert after 3rd node
        // this newNode's next will be 3rd node's next i.e. 4th node
        newNode->next= temp->next;
        
        // 3rd node's next = this newNode
        temp->next = newNode;

    }
}

int calcSize(struct Node* head){
    int size = 0;
    struct Node* temp = head;

    if(temp == NULL)
        return size;

    do{
        size++;
        temp = temp->next;
        
    }while(temp!=head);
    
    return size;
}

void display(struct Node* head){
    // if there are no node in CLL
    if(head == NULL)
        return;
    
    struct Node* temp = head;
    
    //need to take care of circular structure of CLL
    do{
        printf("%d ", temp->data);
        temp = temp->next;
        
    }while(temp!=head);
    printf("\n");
}

int main(){
    
    // first node will be null at creation    
    struct Node* head = NULL;
    
    insertFront(&head,200);
    insertFront(&head,100);

    display(head);
    
    insertEnd(&head, 300);
    insertEnd(&head, 4000);
    
    display(head);
    
    //Inserts after 3rd position
    insertAfterPosition(3,0,&head);
    
    display(head);
  
  	return 0;
}

Output

100 200 
100 200 300 4000 
100 200 300 0 4000

Deletion in a Circular Linked List

The program Covers deletion at the following –

At Front
At end
nth node

Run

#include<stdio.h>
#include<stdlib.h>
// structure for Circular Linked List
struct Node
{
   int data;
   struct Node *next;
};

int calcSize(struct Node* head);

void deleteFront(struct Node** head){
    
    struct Node* temp = *head;
  
    // if there are no nodes in Linked List can't delete
    if(*head == NULL){
        printf("Linked List Empty, nothing to delete");
        return;
    }
    
    // if only 1 node in CLL
    if(temp->next == *head){
        *head = NULL;
        return;
    }
    
    struct Node* curr = *head;
    
    // traverse till last node in CLL
    while(curr->next != *head)
        curr = curr->next;
    
    // assign last node's next to 2nd node in CLL
    curr->next = (*head)->next;

    // move head to next node
    *head = (*head)->next;
    free(temp);
}

void deleteEnd(struct Node** head){
    struct Node* temp = *head;
    struct Node* previous;
    
    // if there are no nodes in Linked List can't delete
    if(*head == NULL){
        printf("Linked List Empty, nothing to delete");
        return;
    }
    
    // if Linked List has only 1 node
    if(temp->next == *head){
        *head = NULL;
        return;
    }
    
    // else traverse to the last node
    while (temp->next != *head) 
    {
        // store previous link node as we need to change its next val
        previous = temp; 
        temp = temp->next; 
    }
    // Curr assign 2nd last node's next to head
    previous->next = *head;
    // delete the last node
    free(temp);
    // 2nd last now becomes the last node
}

void deletePos(struct Node** head, int n){
    
    int size = calcSize(*head);
    
    if(n < 1 || size < n) 
    { 
        printf("Can't delete, %d is not a valid position\n", n); 
    } 
    else if(n == 1) 
        deleteFront(head); 
    else if(n == size) 
        deleteEnd(head); 
    else 
    { 
        struct Node* temp = *head; 
        struct Node* previous; 

        // traverse to the nth node 
        while (--n) 
        { 
            // store previous link node as we need to change its next val 
            previous = temp; 
            temp = temp->next; 
        }
    
        // change previous node's next node to nth node's next node
        previous->next = temp->next;
        // delete this nth node
        free(temp);
    }
}

void insert(struct Node** head, int data)
{
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    
    if(*head == NULL){
        *head = newNode;
        (*head)->next = *head;
        return;
    }
    
    struct Node* curr = *head;
    
    while(curr->next != *head){
        curr = curr->next;
    }
    
    curr->next = newNode;
    newNode->next = *head;
    *head = newNode;
}

int calcSize(struct Node* head){
    int size = 0;
    struct Node* temp = head;

    if(temp == NULL)
        return size;

    do{
        size++;
        temp = temp->next;
        
    }while(temp!=head);
    
    return size;
}

void display(struct Node* head){
    // if there are no node in CLL
    if(head == NULL)
        return;
    
    struct Node* temp = head;
    
    //need to take care of circular structure of CLL
    do{
        printf("%d ", temp->data);
        temp = temp->next;
        
    }while(temp!=head);
    printf("\n");
}

int main(){
    
    // first node will be null at creation    
    struct Node* head = NULL;
    
    insert(&head,10);
    insert(&head,20);
    insert(&head,30);
    insert(&head,40);
    insert(&head,50);
    insert(&head,60);
    insert(&head,70);

    display(head);
    
    deleteFront(&head);

    display(head);
    
    deleteEnd(&head);
    
    display(head);
    
    deletePos(&head, 3);
    
    display(head);

  	return 0;
}