C program to search an element in Circular Linked List

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.

How to search an element in Singly Linked List.

Search an element in 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.

  1. Create a circular linked list of n nodes. Store reference of first node to head.
  2. Input element to search from user. Store it in some variable say key.
  3. To traverse through list, store reference of head node to some variable, say current = head;.
  4. Initialize another variable to keep track of index of current node, say index = 0;.
  5. 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).
  6. 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.
  7. 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