











Circular Linked List Insertion and Deletion Program in C
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; }
Login/Signup to comment