Circular linked lists are a special type of linked list where the last node points back to the first node, forming a circle. Deletion in a circular linked list is an important operation, as it allows you to remove unwanted nodes from the list.

In this tutorial, we will explain deletion at the beginning, end, and at any given location in simple terms with examples.

What is Circular Linked List(CLL)?

A circular linked list (CLL) is a special type of linked list where the last node points back to the first node, forming a circle. This means you can keep moving through the list over and over without stopping. In a singly circular linked list, each node has only one pointer that goes to the next node, while in a doubly circular linked list, each node has two pointers: one for the next node and one for the previous node, so you can move forward or backward easily. You can think of it like a round table, where the last person is connected to the first person, creating a continuous loop.

Why Deletion is Important in Circular Linked Lists ?

Deletion is a crucial operation in circular linked lists because it helps remove unnecessary or unwanted data, keeping the list clean and organized. By deleting nodes that are no longer needed, the list remains efficient and up-to-date, ensuring that operations like insertion and traversal run smoothly. Proper deletion also frees memory, preventing memory leaks that could slow down or crash programs. This operation becomes particularly important in real-time applications such as round-robin scheduling, music playlists, and buffer management, where data needs to be constantly updated and maintained for optimal performance.

Example of Deletion in Circular Linked List

Imagine a music playlist that plays songs in a loop. The playlist is implemented as a circular linked list, where each song is a node:

Node	Song Name
1	Song A
2	Song B
3	Song C
4	Song D

The last song (Song D) points back to the first song (Song A), so the playlist can repeat indefinitely.

1. Deletion at the Beginning

If the user decides to remove the first song (Song A):

• The playlist now starts from Song B, and the last song (Song D) points to Song B.
• The first node is deleted, and the circular structure is maintained.

New playlist: Song B → Song C → Song D → back to Song B

2. Deletion at the End

If the user removes the last song (Song D):

• The second-last song (Song C) now points back to the first song (Song A or Song B, depending on previous deletion).
• The last node is deleted, keeping the circular structure intact.

New playlist: Song A → Song B → Song C → back to Song A

3. Deletion at Any Given Position

If the user wants to remove the second song (Song B):

• The first song’s next pointer is updated to skip Song B and point to Song C.
• Song B is deleted without breaking the circular chain.

New playlist: Song A → Song C → Song D → back to Song A

Advantages of Circular Linked List

Circular linked lists are very good for going through the list again and again because the last node connects back to the first one. This makes it easy to keep looping without starting over. They are helpful in things like process scheduling in computers, multiplayer games, and round-robin tasks, where you need to handle items or players in a repeating order. Compared to arrays, circular linked lists use memory more efficiently because you can add or remove nodes without moving everything around, which is perfect when data changes often.

Algorithm for Deleting a Node from the Beginning of a CLL

1. Check if the list is empty (head == NULL). If yes, deletion is not possible.
2. If only one node exists, delete it and set head = NULL.
3. Otherwise, move the head pointer to the second node.
4. Update the last node’s next pointer to the new head.
5. Free the memory of the old head node.

C Program to Delete a node in circular linked list at Beginning

#include<stdio.h> 
#include<conio.h>
#include<stdlib.h>
struct node{
    int data;
    struct node *next;
    };
struct node *head=NULL;
struct node* createNode(){
    struct node *newNode = (struct node *)malloc(sizeof(struct node));
    return (newNode);
    }
 
void insertNode(){
	struct node *temp,*ptr;
	temp=createNode();
	printf("enter the data you want to insert:");
	scanf("%d",&temp->data);
	temp->next=NULL;
	if(head==NULL){
		head=temp;
		head->next=head;
	}
	else{
		ptr=head;
		while(ptr->next!=head){
			ptr=ptr->next;
		}
	       ptr->next=temp;
	       temp->next=head;
	     }
    }
 
void deleteNodeAtBegin(){
    if(head==NULL){
		printf("list is empty");
	}
	else{
		struct node* temp=head;
        struct node* ptr=head;
        while(ptr->next!=head){
		    ptr =ptr->next;
	    }
        head=head->next;
        ptr ->next=head;
        printf("\n deleted node with value %d",temp->data);
		free(temp);
	    }
    }
void viewList(){
    struct node* temp=head;
	if(temp==NULL){
		printf("list is empty");
	}
	else{
	    printf("Values of Cicular list \n");
		while(temp->next!=head)
		{
			printf("%d\t",temp->data);
			temp=temp->next;
		}
		printf("%d \t",temp->data);
	}
}
 
int menu(){
    int choice;
    printf("\n 1.Add value to the list");
    printf("\n 2.Delete node at Begining");
    printf("\n 3.Travesre/View List");
    printf("\n 4.Exit");
    printf("\n Please enter your choice: \t");
    scanf("%d",&choice);
    return(choice);
}
void main(){
    printf("Delete a node in circular linked list at Beginning");
    while(1){
        switch(menu()){
            case 1:
                insertNode();
                break;
            case 2:
                deleteNodeAtBegin();
                break;
            case 3:
                viewList();
                break;
            case 4:
                exit(0);
            default:
                printf("invalid choice");
        }
    }
    getch();
}

Output:

Delete a node in circular linked list at Beginning
 1.Add value to the list
 2.Delete node at Beginning
 3.Travesre/View List
 4.Exit
 Please enter your choice:      1
enter the data you want to insert:4

 1.Add value to the list
 2.Delete node at Beginning
 3.Travesre/View List
 4.Exit
 Please enter your choice:      1
enter the data you want to insert:3

 1.Add value to the list
 2.Delete node at Beginning
 3.Travesre/View List
 4.Exit
 Please enter your choice:      1
enter the data you want to insert:3

 1.Add value to the list
 2.Delete node at Beginning
 3.Travesre/View List
 4.Exit
 Please enter your choice:      1
enter the data you want to insert:7

 1.Add value to the list
 2.Delete node at Beginning
 3.Traverse/View List
 4.Exit
 Please enter your choice:      3
Values of Circular list 
4       3       3       7 
 1.Add value to the list
 2.Delete node at Beginning
 3.Travesre/View List
 4.Exit
 Please enter your choice:      2

 deleted node with value 4
 1.Add value to the list
 2.Delete node at Beginning
 3.Travesre/View List
 4.Exit
 Please enter your choice:      3
Values of Circular list 
3       3       7 
 1.Add value to the list
 2.Delete node at Beginning
 3.Travesre/View List
 4.Exit
 Please enter your choice:      4

Explanation of Code

1. Struct Definition

struct node{
    int data;
    struct node *next;
};

This code help us in making a node for a linked list in C programming. A linked list is like a chain of boxes, where each box holds some information and points to the next box. In this code, struct node is like a blueprint for each box. The int data; part is where we store a number or value inside the box. The struct node *next part is a pointer or arrow that tells us where the next box in the chain is. Using many nodes connected together like this, we can make a linked list, which allows us to store and organize data efficiently.

struct node *head = NULL;

In a linked list, head is a special pointer that always points to the first node of the list. The line of code means that we are creating a pointer named head of type struct node and setting it to NULL. NULL means that the list is empty right now and doesn’t have any nodes. Later, when we add nodes to the list, head will point to the first node, helping us keep track of the entire linked list.

2. Node Creation

struct node* createNode(){
    struct node *newNode = (struct node *)malloc(sizeof(struct node));
    return (newNode);
}

The line of code is used to create a new node for a linked list. When we want to add a new box (node) to the list, this function allocates memory for it using malloc, which is like reserving space in the computer’s memory. The newNode pointer now points to this newly created node. Finally, the function returns the pointer so we can use it to add the node to the linked list.

3. Insert Node

void insertNode(){
    struct node *temp,*ptr;
    temp=createNode();
    printf("enter the data you want to insert:");
    scanf("%d",&temp->data);
    temp->next=NULL;
}

The line of code is used to add a new node to a linked list. First, it creates a new node by calling createNode() and stores it in the pointer temp. Then, it asks the user to enter the data for that node using scanf. Finally, it sets temp->next = NULL, which means the new node doesn’t point to any other node yet. Later, we can connect this node to the linked list.

    if(head==NULL){
        head=temp;
        head->next=head;
    }

This part of the code checks if the linked list is empty. If head is NULL, it means there are no nodes yet. In that case, we make head point to the new node temp, because now it will be the first node in the list. The line head->next = head makes the node point to itself, which is important for a circular linked list. This way, even with only one node, the list forms a circle.

    else{
        ptr=head;
        while(ptr->next!=head){
            ptr=ptr->next;
        }
        ptr->next=temp;
        temp->next=head;
    }

This part of the code is used when the circular linked list already has some nodes. First, it starts from head and moves through the list using a while loop until it reaches the last node (the node whose next points back to head). Then, it connects the new node temp to the end by setting ptr->next = temp. Finally, it makes the new node point back to head using temp->next = head; so the list remains circular.

4. Delete Node at Beginning

void deleteNodeAtBegin(){
    if(head==NULL){
        printf("list is empty");
    }
    else{
        struct node* temp=head;
        struct node* ptr=head;
        while(ptr->next!=head){
            ptr=ptr->next;
        }
        head=head->next;
        ptr->next=head;
        printf("\n deleted node with value %d",temp->data);
        free(temp);
    }
}

This function is used to delete the first node in a circular linked list. First, it checks if the list is empty (head == NULL). If it is empty, it simply prints “list is empty.” Otherwise, it continues to delete the first node.

It uses two pointers: temp points to the first node, which will be deleted, and ptr is used to find the last node in the circular list. The while loop moves ptr until it reaches the last node (the one whose next points to head). Then, the head pointer is moved to the second node in the list, and the last node’s next pointer is updated to point to this new head. This keeps the list circular. Finally, it prints the value of the deleted node and frees the memory to avoid memory leaks.

5. Traverse/View List

void viewList(){
    struct node* temp=head;
    if(temp==NULL){
        printf("list is empty");
    }
    else{
        printf("Values of Circular list \n");
        while(temp->next!=head){
            printf("%d\t",temp->data);
            temp=temp->next;
        }
        printf("%d \t",temp->data);
    }
}

This function is used to display all the values stored in a circular linked list. First, it checks if the list is empty by seeing if head is NULL. If the list is empty, it uses printf to print “list is empty.” If the list has nodes, it starts from the first node (head) using a temporary pointer temp and goes through each node using a while loop. The loop uses printf to display the data of each node until it reaches the last node, whose next points back to the head. After the loop, it prints the data of the last node as well using printf to show all values in the list.

6. Menu

int menu(){
    int choice;
    printf("\n 1.Add value to the list");
    printf("\n 2.Delete node at Begining");
    printf("\n 3.Travesre/View List");
    printf("\n 4.Exit");
    printf("\n Please enter your choice: \t");
    scanf("%d",&choice);
    return(choice);
}

The menu() function in C is created to display different options for performing operations on a circular linked list and to collect the user’s choice. Inside the function, an integer variable choice is declared to temporarily store the input from the user. Then, four options are displayed on the screen using printf(): option 1 allows the user to add a value to the list, option 2 allows them to delete a node from the beginning of the list, option 3 lets them traverse or view the entire list to see the stored values, and option 4 is used to exit the program. After showing these options, the program asks the user to enter their choice with a message: “Please enter your choice:”.

The entered value is read using scanf(“%d”,&choice); and stored in the choice variable. Finally, the function returns this choice back to the calling function (usually main()), so that the program knows which action the user wants to perform. In short, the menu() function acts like a control panel or command center that guides the user step by step in interacting with the circular linked list program.

7. Main Function

void main(){
    printf("Delete a node in circular linked list at Beginning");
    while(1){
        switch(menu()){
            case 1:
                insertNode();
                break;
            case 2:
                deleteNodeAtBegin();
                break;
            case 3:
                viewList();
                break;
            case 4:
                exit(0);
            default:
                printf("invalid choice");
        }
    }
    getch();
}

The main() function here is the driving force of the circular linked list program, where all the operations are controlled. At the beginning, a message is displayed using printf() to inform the user about the task: “Delete a node in circular linked list at Beginning”. After this, an infinite loop (while(1)) is used so that the program repeatedly shows the menu until the user decides to exit. Inside the loop, the menu() function is called, which displays the options and returns the user’s choice. A switch statement is then used to execute the correct operation based on that choice: if the user enters 1, the program calls insertNode() to add a new value into the circular linked list; if the user enters 2, the deleteNodeAtBegin() function is called to remove the first node of the list; if the user enters 3, the viewList() function is executed to display all the elements of the circular list; and if the user enters 4, the program calls exit(0) which safely stops the execution. If the user enters any number other than 1–4, the default case is triggered, and a message “invalid choice” is displayed. Finally, getch() is kept after the loop to wait for a key press, ensuring the output remains visible on the screen before the program closes. Thus, this main() function serves as the controller of the program, connecting user input with linked list operations.

Time Complexity

Case	Condition	Operations	Time Complexity
Best Case	List empty OR only one node (head==NULL or head->next==head)	Just check and delete	O(1)
Average Case	List has n nodes (random size)	Traverse to last node, update links, delete head	O(n)
Worst Case	List has maximum n nodes (need full traversal)	Full traversal of list to find last node, then delete	O(n)

Space Complexity

Case	Condition	Extra Space Used	Space Complexity
Empty List	head == NULL	Only a temporary pointer check	O(1)
Single Node	head->next == head	One pointer (temp) before free	O(1)
Multiple Nodes	More than one node	Two pointers (temp, last)	O(1)

Delete a node in Circular linked list at End

Algorithm

1. Check if the list is empty (head == NULL).
2. If only one node exists, delete it and set head = NULL.
3. Traverse the list to reach the second last node.
4. Update its next pointer to point to head.
5. Free the memory of the last node.

C program to delete a node in Circular linked list at End

#include<stdio.h> 
#include<conio.h>
#include<stdlib.h>
struct node{
    int data;
    struct node *next;
    };
struct node *head=NULL;
struct node* createNode(){
    struct node *newNode = (struct node *)malloc(sizeof(struct node));
     
return (newNode);
    }
 
void insertNode(){
	struct node *temp,*ptr;
	temp=createNode();
	printf("enter the data you want to insert:");
	scanf("%d",&temp->data);
	temp->next=NULL;
	if(head==NULL){
		head=temp;
		head->next=head;
	}
	else{
		ptr=head;
		while(ptr->next!=head){
			ptr=ptr->next;
		}
	       ptr->next=temp;
	       temp->next=head;
	     }
    }
 
void deleteNodeAtEnd(){
	struct node *temp,*secondLast;
	if(head==NULL){
		printf("list is empty");
	}
	else{
		temp=head;
		secondLast=head;
		while(temp->next!=head){
			secondLast=temp;
			temp=temp->next;
		}
		if(temp==head){
			head=NULL;
		}
		else{
			secondLast->next=head;
		}
		free(temp);
	}
 }
void viewList(){
    struct node* temp=head;
	if(temp==NULL){
		printf("list is empty");
	}
	else{
	    printf("Values of Cicular list \n");
		while(temp->next!=head)
		{
			printf("%d\t",temp->data);
			temp=temp->next;
		}
		printf("%d \t",temp->data);
	}
}
 
int menu(){
    int choice;
    printf("\n 1.Add value to the list");
    printf("\n 2.Delete node at End");
    printf("\n 3.Travesre/View List");
    printf("\n 4. exit");
    printf("\n Please enter your choice: \t");
    scanf("%d",&choice);
    return(choice);
}
void main(){
    printf("Delete a node in circular linked list at End");
    while(1){
        switch(menu()){
            case 1:
                insertNode();
                break;
            case 2:
                deleteNodeAtEnd();
                break;
            case 3:
                viewList();
                break;
            case 4:
                exit(0);
            default:
                printf("invalid choice");
        }
    }
        getch();
    }

Output:

Delete a node in circular linked list at End
 1.Add value to the list
 2.Delete node at End
 3.Travesre/View List
 4. exit
 Please enter your choice:      1
enter the data you want to insert:3

 1.Add value to the list
 2.Delete node at End
 3.Travesre/View List
 4. exit
 Please enter your choice:      1
enter the data you want to insert:6

 1.Add value to the list
 2.Delete node at End
 3.Travesre/View List
 4. exit
 Please enter your choice:      1
enter the data you want to insert:3

 1.Add value to the list
 2.Delete node at End
 3.Travesre/View List
 4. exit
 Please enter your choice:      1
enter the data you want to insert:7

 1.Add value to the list
 2.Delete node at End
 3.Travesre/View List
 4. exit
 Please enter your choice:      3
Values of Cicular list 
3       6       3       7 
 1.Add value to the list
 2.Delete node at End
 3.Travesre/View List
 4. exit
 Please enter your choice:      2

 1.Add value to the list
 2.Delete node at End
 3.Travesre/View List
 4. exit
 Please enter your choice:      3 
Values of Cicular list 
3       6       3 
 1.Add value to the list
 2.Delete node at End
 3.Travesre/View List
 4. exit
 Please enter your choice:      4

Explanation of Code

1. Structure of Node

struct node{
    int data;
    struct node *next;
};

This code is used to make a node in a linked list. A node has two parts: data, which stores a number, and next, which points to the next node. When many nodes are connected using next, they form a linked list, which is like a chain of connected nodes. For example, one node may have the number 10 and point to another node with 20, which points to another node with 30.

2. Global Head Pointer

struct node *head=NULL

This line makes a special pointer called head. The job of head is to remember the first node of the linked list. Right now, it is set to NULL, which means the linked list is empty and has no nodes yet. Later, when we add the first node, head will point to it so that we can always find the start of the list.

3. Create Node Function

struct node* createNode(){
    struct node *newNode = (struct node *)malloc(sizeof(struct node));
    return (newNode);
}

This function is used to make a new node in the linked list. Inside the function, malloc is used to give memory (space in the computer) for the new node. The pointer newNode keeps the address of this fresh node. Finally, the function returns this new node, so we can use it in our program to add data and connect it with other nodes.

4. Insert Node at End

void insertNode(){
    struct node *temp,*ptr;
    temp=createNode();
    printf("enter the data you want to insert:");
    scanf("%d",&temp->data);
    temp->next=NULL;

    if(head==NULL){   // First node
        head=temp;
        head->next=head;  // points to itself
    }
    else{  // Traverse to last node
        ptr=head;
        while(ptr->next!=head){
            ptr=ptr->next;
        }
        ptr->next=temp;   // link last node to new node
        temp->next=head;  // maintain circular link
    }
}

The insertNode() function starts by creating a new node using temp = createNode(), which asks the computer to make space for a new node. Then printf(“enter the data you want to insert:”); shows a message to the user to type a number, and scanf("%d",&temp->data); reads that number and stores it in the new node. temp->next = NULL; sets the next pointer to NULL because the node is not linked yet. The if (head == NULL) part checks if the list is empty. If it is empty, head = temp; makes this new node the first node, and head->next = head; makes it point to itself to form a circle. If the list is not empty, ptr = head; starts a pointer at the first node, and the while(ptr->next != head) loop moves it to the last node. Then ptr->next = temp; links the last node to the new node, and temp->next = head; makes the new node point back to the first node, keeping the circular linked list complete.

5. Delete Node at End

void deleteNodeAtEnd(){
    struct node *temp,*secondLast;
    if(head==NULL){
        printf("list is empty");
    }
    else{
        temp=head;
        secondLast=head;
        while(temp->next!=head){  // traverse to last
            secondLast=temp;
            temp=temp->next;
        }
        if(temp==head){   // only one node
            head=NULL;
        }
        else{   // More than one node
            secondLast->next=head;   // second last points to head
        }
        free(temp);   // delete last node
    }
}

The deleteNodeAtEnd() function is used to remove the last node from a circular linked list. First, it checks if the list is empty with if(head == NULL) and prints “list is empty” if there are no nodes. If the list has nodes, two pointers temp and secondLast are set to head. The while(temp->next != head) loop moves temp to the last node and secondLast to the second-last node. Then, if (temp == head) checks if there is only one node; if so, head = NULL makes the list empty. If there are more nodes, secondLast->next = head makes the second-last node point back to the head, keeping the circular structure. Finally, free(temp) deletes the last node from memory so it does not use space anymore

6. Traverse / View List

void viewList(){
    struct node* temp=head;
    if(temp==NULL){
        printf("list is empty");
    }
    else{
        printf("Values of Cicular list \n");
        while(temp->next!=head){
            printf("%d\t",temp->data);
            temp=temp->next;
        }
        printf("%d \t",temp->data); // print last node
    }
}

The viewList() function is used to see all the values stored in a circular linked list. First, it checks if the list is empty. If there are no nodes, it prints “list is empty.” If the list has nodes, it starts from the first node and goes through each node one by one using a loop. For each node, it prints the value stored in it. The loop stops when it reaches the last node, and then it prints the last node’s value separately. This way, all the values in the circular linked list are displayed, showing the full circle of nodes.

7. Menu Function

int menu(){
    int choice;
    printf("\n 1.Add value to the list");
    printf("\n 2.Delete node at End");
    printf("\n 3.Travesre/View List");
    printf("\n 4. exit");
    printf("\n Please enter your choice: \t");
    scanf("%d",&choice);
    return(choice);
}

The menu() function is used to show options to the user in the circular linked list program. It prints a list of actions on the screen, like adding a value to the list, deleting a node at the end, viewing all the nodes, or exiting the program. Then it asks the user to type their choice using scanf, which reads the number entered and saves it in a variable called choice. Finally, the function returns this choice so the program knows which action the user wants to do next.

8. Main Function

void main(){
    printf("Delete a node in circular linked list at End");
    while(1){
        switch(menu()){
            case 1:
                insertNode();
                break;
            case 2:
                deleteNodeAtEnd();
                break;
            case 3:
                viewList();
                break;
            case 4:
                exit(0);
            default:
                printf("invalid choice");
        }
    }
    getch();
}

The main() function is where the program starts running. First, it prints a message telling the user that the program can delete a node at the end of a circular linked list. Then it runs a forever loop using while(1) so the program keeps showing the menu again and again until the user chooses to exit. Inside the loop, the switch statement checks what the user chooses from the menu. If the user chooses 1, it calls the insertNode() function to add a new node.

If the user chooses 2, it calls deleteNodeAtEnd() to remove the last node. If the user chooses 3, it calls viewList() to display all nodes. If the user chooses 4, the program exits. If the user enters any other number, it prints “invalid choice.” Finally, getch() waits for a key press so the program does not close immediately.

Time & Space Complexity

Operation	Best Case	Average Case	Worst Case	Space Complexity
Insert at Beginning	O(1)	O(1)	O(1)	O(1)
Insert at End	O(1) (if tail is maintained) O(n) (if traversing)	O(n)	O(n)	O(1)
Delete from Beginning	O(1)	O(1)	O(1)	O(1)
Delete from End	O(1) (if tail & prev maintained) O(n) (if traversing)	O(n)	O(n)	O(1)
Traverse Entire List	O(n)	O(n)	O(n)	O(1)
Search for a Node	O(1) (if first element matches)	O(n)	O(n)	O(1)

C Program to Delete a node in circular linked list at Given Location

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
};

struct node *head = NULL;

struct node* createNode() {
    struct node *newNode = (struct node *)malloc(sizeof(struct node));
    return newNode;
}

void insertNode() {
    struct node *temp, *ptr;
    temp = createNode();
    printf("Enter the data you want to insert: ");
    scanf("%d", &temp->data);
    temp->next = NULL;

    if (head == NULL) {
        head = temp;
        head->next = head;
    } else {
        ptr = head;
        while (ptr->next != head) {
            ptr = ptr->next;
        }
        ptr->next = temp;
        temp->next = head;
    }
}

void deleteNodeAtPosition(int position) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }

    struct node *temp = head, *prev = NULL;
    int count = 1;

    // Case 1: Delete head node
    if (position == 1) {
        int deletedData = head->data;
        if (head->next == head) {
            free(head);
            head = NULL;
        } else {
            struct node *last = head;
            while (last->next != head)
                last = last->next;
            last->next = head->next;
            temp = head;
            head = head->next;
            free(temp);
        }
        printf("Deleted node value: %d\n", deletedData);
        return;
    }

    // Traverse to the node at (position - 1)
    while (count < position && temp->next != head) {
        prev = temp;
        temp = temp->next;
        count++;
    }

    if (count != position) {
        printf("Invalid position.\n");
        return;
    }

    int deletedData = temp->data;
    prev->next = temp->next;
    free(temp);
    printf("Deleted node value: %d\n", deletedData);
}


void viewList() {
    struct node* temp = head;
    if (temp == NULL) {
        printf("List is empty.\n");
    } else {
        printf("Values of Circular list:\n");
        while (temp->next != head) {
            printf("%d\t", temp->data);
            temp = temp->next;
        }
        printf("%d\t", temp->data);
    }
}

int menu() {
    int choice;
    printf("\n\n***** MENU *****");
    printf("\n 1. Add value to the list");
    printf("\n 2. Delete node from given position");
    printf("\n 3. Traverse/View List");
    printf("\n 4. Exit");
    printf("\n Please enter your choice: ");
    scanf("%d", &choice);
    return choice;
}

void main() {
    printf("Circular Linked List Operations\n");
    while (1) {
        switch (menu()) {
            case 1:
                insertNode();
                break;
            case 2:{
                int pos;
                printf("Enter the position to delete: ");
                scanf("%d", &pos);
                deleteNodeAtPosition(pos);
                break;
            }
            case 3:
                viewList();
                break;
            case 4:
                exit(0);
            default:
                printf("Invalid choice.\n");
        }
    }
    getch();
}

Output

Circular Linked List Operations


***** MENU *****
 1. Add value to the list
 2. Delete node from given position
 3. Traverse/View List
 4. Exit
 Please enter your choice: 1
Enter the data you want to insert: 6


***** MENU *****
 1. Add value to the list
 2. Delete node from given position
 3. Traverse/View List
 4. Exit
 Please enter your choice: 1
Enter the data you want to insert: 3


***** MENU *****
 1. Add value to the list
 2. Delete node from given position
 3. Traverse/View List
 4. Exit
 Please enter your choice: 1
Enter the data you want to insert: 4


***** MENU *****
 1. Add value to the list
 2. Delete node from given position
 3. Traverse/View List
 4. Exit
 Please enter your choice: 1
Enter the data you want to insert: 8


***** MENU *****
 1. Add value to the list
 2. Delete node from given position
 3. Traverse/View List
 4. Exit
 Please enter your choice: 3
Values of Circular list:
6       3       4       8

***** MENU *****
 1. Add value to the list
 2. Delete node from given position
 3. Traverse/View List
 4. Exit
 Please enter your choice: 2
Enter the position to delete: 2
Deleted node value: 3


***** MENU *****
 1. Add value to the list
 2. Delete node from given position
 3. Traverse/View List
 4. Exit
 Please enter your choice: 4

Explanation of Code

1. Structure Definition

struct node {
    int data;
    struct node *next;
};

The code is used to make a node for a linked list. A node is like a small container that has two parts: data, which stores a number, and next, which points to the next node in the list. When many nodes are connected using next, they form a linked list, which is like a chain of nodes. For example, one node can have the number 10 and point to another node with 20, which points to another node with 30, forming a chain of nodes.

struct node *head = NULL;

This line creates a special pointer called head. The head is used to remember the first node in a linked list. Right now, it is set to NULL, which means the list is empty and has no nodes yet. Later, when we add the first node, head will point to it, so we can always find the start of the list.

2. Node Creation

struct node* createNode() {
    struct node *newNode = (struct node *)malloc(sizeof(struct node));
    return newNode;
}

The createNode() function is used to make a new node for the linked list. Inside the function, malloc asks the computer to give memory (space) for the new node. The pointer newNode stores the address of this new node so we can use it later. Finally, the function returns this new node, so it can be added to the linked list and connected with other nodes.

3. Insert Node at End

void insertNode() {
    struct node *temp, *ptr;
    temp = createNode();
    printf("Enter the data you want to insert: ");
    scanf("%d", &temp->data);
    temp->next = NULL;

    if (head == NULL) { // if list is empty
        head = temp;
        head->next = head; // first node points to itself
    } else {
        ptr = head;
        while (ptr->next != head) { // move to last node
            ptr = ptr->next;
        }
        ptr->next = temp; // link last node to new node
        temp->next = head; // new node links back to head
    }
}

The insertNode() function is used to add a new node to a circular linked list. First, it creates a new node using createNode() and asks the user to enter a number to store in it. The new node’s next pointer is set to NULL because it is not linked yet. Then the program checks if the list is empty. If the list is empty, the new node becomes the first node and points to itself, making the list circular. If the list already has nodes, the program moves to the last node in the list and links it to the new node. Finally, the new node is made to point back to the head, so the circular structure is maintained.

4. Delete Node at a Given Position

void deleteNodeAtPosition(int position) {
    if (head == NULL) {
        printf("List is empty.\n");
        return;
    }

    struct node *temp = head, *prev = NULL;
    int count = 1;

    // Case 1: Delete head node
    if (position == 1) {
        int deletedData = head->data;
        if (head->next == head) { // only one node
            free(head);
            head = NULL;
        } else { // more than one node
            struct node *last = head;
            while (last->next != head) // move to last node
                last = last->next;
            last->next = head->next; // link last node to 2nd node
            temp = head;
            head = head->next; // update head
            free(temp);
        }
        printf("Deleted node value: %d\n", deletedData);
        return;
    }

    // Case 2: Delete non-head node
    while (count < position && temp->next != head) {
        prev = temp;
        temp = temp->next;
        count++;
    }

    if (count != position) { // if position > list length
        printf("Invalid position.\n");
        return;
    }

    int deletedData = temp->data;
    prev->next = temp->next; // unlink node
    free(temp);
    printf("Deleted node value: %d\n", deletedData);
}

The deleteNodeAtPosition() function is used to remove a node from any position in a circular linked list. First, it checks if the list is empty and prints “List is empty” if there are no nodes. Then it uses two pointers, temp to find the node to delete and prev to remember the node before it. If the position is 1, it means the head node should be deleted. If there is only one node, it deletes it and makes the list empty.

If there are more nodes, it finds the last node, links it to the second node, updates the head, and deletes the first node. For any other position, it moves through the list until it reaches the node to delete. If the position is invalid (greater than the number of nodes), it prints “Invalid position.” Otherwise, it unlinks the node from the list, deletes it, and prints its value.

5. Traverse / View List

void viewList() {
    struct node* temp = head;
    if (temp == NULL) {
        printf("List is empty.\n");
    } else {
        printf("Values of Circular list:\n");
        while (temp->next != head) {
            printf("%d\t", temp->data);
            temp = temp->next;
        }
        printf("%d\t", temp->data); // print last node
    }
}

The viewList() function is used to see all the numbers stored in a circular linked list. First, it checks if the list is empty and prints “List is empty” if there are no nodes. If the list has nodes, it starts from the first node using a temporary pointer. Then it goes through each node one by one in a loop, printing the number stored in each node. The loop stops when it reaches the last node, and the last node’s number is printed separately. This way, all numbers in the circular linked list are displayed, showing the full circle of nodes.

6. Menu Function

int menu() {
    int choice;
    printf("\n\n***** MENU *****");
    printf("\n 1. Add value to the list");
    printf("\n 2. Delete node from given position");
    printf("\n 3. Traverse/View List");
    printf("\n 4. Exit");
    printf("\n Please enter your choice: ");
    scanf("%d", &choice);
    return choice;
}

The menu() function is used to show a list of options to the user in the circular linked list program. It prints a menu on the screen with choices like adding a new number to the list, deleting a node from a specific position, viewing all the nodes, or exiting the program. Then it asks the user to type a number for their choice, and scanf reads this number and saves it in a variable called choice. Finally, the function returns the choice so the program knows what action the user wants to perform next.

7. Main Function

void main() {
    printf("Circular Linked List Operations\n");
    while (1) {
        switch (menu()) {
            case 1:
                insertNode();
                break;
            case 2:{
                int pos;
                printf("Enter the position to delete: ");
                scanf("%d", &pos);
                deleteNodeAtPosition(pos);
                break;
            }
            case 3:
                viewList();
                break;
            case 4:
                exit(0);
            default:
                printf("Invalid choice.\n");
        }
    }
    getch();
}

The main() function is where the program starts running. First, it prints a message to tell the user that this program performs circular linked list operations. Then it uses a forever loop so the program keeps running until the user decides to exit. Inside the loop, it calls the menu() function to show the options to the user. If the user chooses 1, it calls insertNode() to add a new node.

If the user chooses 2, it asks for the position of the node to delete and calls deleteNodeAtPosition() to remove that node. If the user chooses 3, it calls viewList() to show all the nodes. If the user chooses 4, the program stops running. If the user enters any other number, it prints “Invalid choice.”

Time & Space Complexity

Operation	Best Case	Average Case	Worst Case	Space Complexity
Insert at end	O(1)	O(n)	O(n)	O(1)
Delete at position (head)	O(1)	O(n)	O(n)	O(1)
Delete at position (non-head)	O(n)	O(n)	O(n)	O(1)
Traverse/View List	O(n)	O(n)	O(n)	O(1)