What is Circular Linked List ?

A circular linked list is a special case of the linked list where in the last node points back to the first node, creating a loop. In contrast to a singly linked list, it is possible to traverse indefinitely unless interrupted externally. This data structure finds use in applications such as round-robin scheduling, buffer management, and real-time systems.

Construction: Nodes are created and connected in a way that the next pointer of the last node is made to point towards the head node.

Traversal: From the head, nodes are traversed one after another, and this process continues until the head node is accessed again.

👉It helps in the accessibility of each node, and traversal is efficient without any NULL condition like in a regular linked list.

Algorithm

1. Start.
2. Create a new node and input its data.
3. If list is empty: new node points to itself and becomes head.
4. If list is not empty: traverse to last node, insert new node, and link it to head.
5. To traverse → start from head and print node values until returning to head.
6. End.

Program to Create and Traverse nodes in C

#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 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.Travesre/View List");
    printf("\n 3.Exit");
    printf("\n Please enter your choice: \t");
    scanf("%d",&choice);
    return(choice);
}
void main(){
    printf("Program to Create and Traverse nodes in Circular linked list");
    while(1){
        switch(menu()){
            case 1:
                insertNode();
                break;
            case 2:
                viewList();
                break;
            case 3:
                exit(0);
            default:
                printf("invalid choice");
        }
    }
        getch();
    }

Output

Program to Create and Traverse nodes in Circular linked list
 1.Add value to the list
 2.Travesre/View List
 3.Exit
 Please enter your choice:      1
enter the data you want to insert:4

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

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

 1.Add value to the list
 2.Travesre/View List
 3.Exit
 Please enter your choice:      1
enter the data you want to insert:9

 1.Add value to the list
 2.Travesre/View List
 3.Exit
 Please enter your choice:      2
Values of Cicular list 
4       2       7       9 
 1.Add value to the list
 2.Travesre/View List
 3.Exit
 Please enter your choice:      3

Explanation of Code

1. Structure Definition

struct node {
    int data;
    struct node *next;
};
struct node *head = NULL;

In the above code, a structure named node is defined to represent each element of a singly linked list. Each node contains an integer field data to store the value and a pointer next that points to the next node in the list. Additionally, a pointer head is declared and initialized to NULL; this pointer represents the first node of the linked list, and its initial NULL value indicates that the list is empty at the beginning.

2. Node Creation

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

In the above code, a function createNode is defined to create a new node for the linked list. Inside the function, memory is dynamically allocated using malloc for a new node of type struct node, and a pointer newNode is assigned to this memory. The function then returns this pointer, which can be used to initialize the node’s data and next pointer when adding it to the list.

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) {  // traverse to last node
            ptr = ptr->next;
        }
        ptr->next = temp;         // link last node to new node
        temp->next = head;        // new node points to head
    }
}

In the above code, the insertNode function is used to add a new node to a circular linked list. First, it creates a new node using createNode and reads the data from the user. The new node’s next pointer is initially set to NULL. If the list is empty (head == NULL), the new node becomes the head, and its next pointer points to itself, forming a single-node circular list. If the list is not empty, the function traverses to the last node (whose next points to the head) and links it to the new node. Finally, the new node’s next pointer is set to point back to the head, maintaining the circular structure of the list.

4. 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
    }
}

In the above code, the viewList function is used to display all the elements of a circular linked list. It starts by creating a temporary pointer temp pointing to the head. If the list is empty (head == NULL), it prints a message indicating that the list is empty. Otherwise, it traverses the list starting from the head and prints the data of each node. The traversal continues until temp->next points back to the head, which indicates the last node. Finally, it prints the data of the last node, ensuring that all nodes in the circular list are displayed.

5. Menu Function

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

In the above code, the menu function displays a simple interactive menu for the user to work with the circular linked list. It shows three options: adding a value to the list, viewing or traversing the list, and exiting the program. The function then prompts the user to enter their choice, reads the input using scanf, and returns the selected option as an integer. This allows the user to interactively perform different operations on the circular linked list.

6. Main Function

void main() {
    printf("Program to Create and Traverse nodes in Circular Linked List\n");
    while (1) {
        switch(menu()) {
            case 1:
                insertNode();
                break;
            case 2:
                viewList();
                break;
            case 3:
                exit(0);
            default:
                printf("Invalid choice\n");
        }
        getch();
    }
}

In the above code, the main function serves as the driver for the circular linked list program. It starts by printing a welcome message. Then, it enters an infinite loop (while(1)) that repeatedly displays the menu and performs actions based on the user’s choice. If the user selects 1, it calls insertNode() to add a new node to the list. If the user selects 2, it calls viewList() to traverse and display the values in the list. Choosing 3 exits the program, while any other input prints “Invalid choice”. The getch() function pauses the program after each operation, allowing the user to view the output before continuing.

Time & Space Complexity