Searching in a circular linked list means finding out if a specific value, commonly referred to as a key, occurs within the list. In contrast to a linear linked list, a circular linked list has its last node point towards the first node, thus there is no NULL to mark the list end. Continuous traversal is made possible by this particular structure, but at the same time, it needs to be handled with care to prevent infinite loops. To search efficiently, one tends to begin at the front of the list and inspect each node’s data one by one. The traversal is continued until the key is located or until the traversal reaches the front again, which means the whole list has been traversed. Care should be taken in instances of:

Empty list: In case the list contains no nodes, the search must quickly determine that the key does not exist.

Single-node list: Because the node is self-referential, the algorithm will need to examine this node as a final step.

General case: For multi-node lists, the traversal progresses node by node while verifying data at every step so that the loop will terminate once the head node is reached once more. Due to its circular character, looking in such a list ensures each item is examined once only, avoiding infinite looping. Due to this, circular linked lists are especially ideal for uses such as round-robin scheduling, buffer management, and cyclic queues, in which repeated traversal is frequent.

Searching in Circular Linked List

Algorithm

1. Start
2. If head == NULL, print "Linked List is empty" and stop.
3. Input the data to search.
4. Initialize temp = head, pos = 1, and flag = 0.
5. Repeat until we return back to head:
   • If temp->data == data:
     • Print "Value found at position pos".
     • Set flag = 1, and stop.
   • Else move temp = temp->next and increment pos.
6. If after traversal flag == 0, print "Value not found".
7. End

C Program

#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 search(){
	struct node *temp;
	int data,i=0,flag;
	temp=head;
	if(temp==NULL)
		printf("Linked List is empty");
	else{
		printf("Enter the data you want to search:");
		scanf("%d",&data);
		if(temp->next==head){
		    printf("Value founded at location %d " ,i+1);
		}
		while(temp!=NULL){
			if(temp->data==data){
				printf("Value founded at location %d " ,i+1);
				flag=0;
				break;
			}
			else if(temp->next==head){
				printf("value not found\n");
				break;
			}else{
			    flag=1;
			}
			i++;
			temp=temp->next;
		}
		if(flag==1){
			printf("value not found\n");
		}

		}
	}
 
int menu(){
    int choice;
    printf("\n 1.Add value to the list");
    printf("\n 2.Search an element");
    printf("\n 3.Exit");
    printf("\n Please enter your choice: \t");
    scanf("%d",&choice);
    return(choice);
}
void main(){
    printf("Program for Searching in Circular Linked List");
    while(1){
        switch(menu()){
            case 1:
                insertNode();
                break;
            case 2:
                search();
                break;
            case 3:
                exit(0);
            default:
                printf("invalid choice");
        }
    }
        getch();
    }

Output:

Program for Searching in Circular Linked List
 1.Add value to the list
 2.Search an element
 3.Exit
 Please enter your choice:      1
enter the data you want to insert:5

 1.Add value to the list
 2.Search an element
 3.Exit
 Please enter your choice:      1
enter the data you want to insert:8

 1.Add value to the list
 2.Search an element
 3.Exit
 Please enter your choice:      1
enter the data you want to insert:6

 1.Add value to the list
 2.Search an element
 3.Exit
 Please enter your choice:      2
Enter the data you want to search:8
Value founded at location 2 
 1.Add value to the list
 2.Search an element
 3.Exit
 Please enter your choice:      3

Explanation of Code

1. Structure Definition

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

• Each node contains:
  • data: integer value
  • next: pointer to the next node
• head is a global pointer pointing to the first node of the circular linked list.

2. Node Creation

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

• Dynamically allocates memory for a new node using malloc.
• Returns pointer to the newly created node.

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

• If list is empty → first node points to itself.
• Otherwise → traverse to the last node and insert before head.

4. Search Node

void search() {
    struct node *temp;
    int data, i = 1, flag = 0;

    if (head == NULL) {
        printf("Linked List is empty\n");
        return;
    }

    printf("Enter the data you want to search: ");
    scanf("%d", &data);
    temp = head;

    do {
        if (temp->data == data) {
            printf("Value found at location %d\n", i);
            flag = 1;
            break;
        }
        temp = temp->next;
        i++;
    } while (temp != head);

    if (flag == 0) {
        printf("Value not found\n");
    }
}

• Traverses the circular linked list starting from head.
• Compares each node’s data with the input.
• If found → prints location. Otherwise → prints “not found”.

5. Menu Function

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

• Provides user choices → insert, search, or exit.

6. Main Function

void main() {
    printf("Program for Searching in Circular Linked List");
    while (1) {
        switch (menu()) {
            case 1:
                insertNode();
                break;
            case 2:
                search();
                break;
            case 3:
                exit(0);
            default:
                printf("Invalid choice");
        }
    }
    getch();
}

• Runs infinitely until user selects Exit.
• Calls respective functions based on user’s choice.

Time & Space Complexity