Write a C program to create a Circular Linked List of n nodes and search an element in Circular Linked List. How to search an element by key in Circular Linked List.
In my previous posts, I have explained how to perform search on singly linked list. In this example I will explain you how to perform search operation on Circular Linked List.
Required knowledge
Do while loop, Functions, Pointers, Structures, Dynamic Memory Allocation
Logic to search an element in Circular Linked List
Step by step descriptive logic to search an element in Circular Linked List.
- Create a circular linked list of n nodes. Store reference of first node to head.
- Input element to search from user. Store it in some variable say key.
- To traverse through list, store reference of head node to some variable, say
current = head;. - Initialize another variable to keep track of index of current node, say
index = 0;. - If current node does not points to any node. Means
if (current == NULL)then simply print node does not contain element (if using function return -1). - If current node is not empty and it contains key. Then you got the node, hence print current index and terminate. Otherwise move current node ahead i.e.
current = current->next;and increment index. - Repeat step 5-6 till once again reached head node i.e.
while (current != head);.
Program to search an element in Circular Linked List
/**
* C program to search an element in a Circular Linked List
*/
#include <stdio.h>
#include <stdlib.h>
/* Basic node structure */
struct node {
int data;
struct node * next;
};
/* Function declaration */
void createList(struct node **head, int n);
void displayList(struct node *head);
int search(struct node *head, int key);
int main()
{
int n, choice, index;
struct node *head = NULL;
/*
* Run forever until user chooses 0
*/
while(choice != 0)
{
printf("--------------------------------------------\n");
printf(" CIRCULAR LINKED LIST PROGRAM \n");
printf("--------------------------------------------\n");
printf("1. Create List\n");
printf("2. Display list\n");
printf("3. Search element\n");
printf("0. Exit\n");
printf("--------------------------------------------\n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter total node to create: ");
scanf("%d", &n);
createList(&head, n);
break;
case 2:
displayList(head);
getchar(); // Hold screen
getchar(); // Hold screen
break;
case 3:
printf("Enter element to search: ");
scanf("%d", &n);
index = search(head, n);
if (index == -1)
printf("%d not found in list.\n", n);
else
printf("%d found at %d position.\n", n, (index + 1));
getchar(); // Hold screen
getchar(); // Hold screen
break;
case 0:
printf("Exiting from application");
exit(0);
break;
default:
printf("Error! Invalid choice. Please choose between 0-3");
}
printf("\n\n\n\n\n");
}
return 0;
}
/**
* Function to search an element in list.
* Returns index of element if exists in list,
* otherwise returns -1.
*/
int search(struct node *head, int key)
{
int index = 0;
struct node *current = head;
// Iterate till end of list
do
{
// Nothing to look into
if (current == NULL)
return;
if (current->data == key)
return index;
current = current->next;
index++;
} while (current != head);
// Element not found in list
return -1;
}
/**
* Creates a circular linked list of n nodes.
*/
void createList(struct node **head, int n)
{
int i, data;
struct node *prevNode, *newNode;
prevNode = NULL;
newNode = NULL;
/* Creates and links rest of the n-1 nodes */
for(i=1; i<=n; i++)
{
// Create a new node
newNode = (struct node *) malloc(sizeof(struct node));
printf("Enter data of %d node: ", i);
scanf("%d", &data);
newNode->data = data;
newNode->next = NULL;
// Link the previous node with newly created node
if (prevNode != NULL)
prevNode->next = newNode;
// Move the previous node ahead
prevNode = newNode;
// Link head node if not linked
if (*head == NULL)
*head = newNode;
}
// Link last node with first node
prevNode->next = *head;
printf("\nCIRCULAR LINKED LIST CREATED SUCCESSFULLY\n");
}
/**
* Display node content of circular linked list
*/
void displayList(struct node *head)
{
struct node *current;
int n = 1;
// Nothing to print in list
if(head == NULL)
{
printf("List is empty.\n");
return;
}
current = head;
printf("DATA IN THE LIST:\n");
do
{
// Print current node
printf("Data %d = %d\n", n++, current->data);
// Move to next node
current = current->next;
} while (current != head);
}--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Search element
0. Exit
--------------------------------------------
Enter your choice : 1
Enter total node to create: 4
Enter data of 1 node: 10
Enter data of 2 node: 20
Enter data of 3 node: 30
Enter data of 4 node: 40
CIRCULAR LINKED LIST CREATED SUCCESSFULLY
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Search element
0. Exit
--------------------------------------------
Enter your choice : 2
DATA IN THE LIST:
Data 1 = 10
Data 2 = 20
Data 3 = 30
Data 4 = 40
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Search element
0. Exit
--------------------------------------------
Enter your choice : 3
Enter element to search: 20
20 found at 2 position.
--------------------------------------------
CIRCULAR LINKED LIST PROGRAM
--------------------------------------------
1. Create List
2. Display list
3. Search element
0. Exit
--------------------------------------------
Enter your choice : 0
Exiting from application