C program to search an element in linked list

Categories Data Structures 7 mins read

Search is one of the most common operation on performed any data structure. In this post I will explain how to search an element in linked list (iterative and recursive) using C program. I will explain both ways to search, how to search an element in linked list using loop and recursion.

Write a C program to create a function to search an element in linked list. If element exists in the linked list then, it should return its index otherwise -1.

Required knowledge

Singly linked list, Pointers, Structures, Dynamic memory allocation

Let us suppose the node structure as

struct node
{
    int data;          // Data
    struct node *next; // Address
} * head;

Where head is a pointer to first node.

Note: To keep this post short, readable and quick to consume. I am not going to explain logic to create and traverse list. You can read a detailed post on how to create and traverse a linked list.

Search an element in linked list is fairly similar to how you search an element in arrays. Here we will learn to perform linear search on singly linked list.

Step by step descriptive logic to search an element in linked list.

  1. Input element to search from user. Store it in some variable say keyToSearch.
  2. Declare two variable one to store index of found element and other to iterate through list. Say index = 0; and struct node *curNode = head;
  3. If curNode is not NULL and its data is not equal to keyToSearch. Then, increment index and move curNode to its next node.
  4. Repeat step 3 till curNode != NULL and element is not found, otherwise move to 5th step.
  5. If curNode is not NULL, then element is found hence return index otherwise -1.

Program to search an element in linked list

/**
 * C program to search an element by key in Singly Linked List.
 */
#include <stdio.h>
#include <stdlib.h>

/* Node structure */
struct node
{
    int data;          // Data
    struct node *next; // Address
} * head;


/* Function declaration */
void createList(int n);
void displayList();
int  search(int key);


int main()
{
    int n, keyToSearch, index;

    // Input node count to create
    printf("Enter number of node to create: ");
    scanf("%d", &n);

    createList(n);

    // Display list
    printf("\nData in list: \n");
    displayList();

    // Input element to search from user.
    printf("\nEnter element to search: ");
    scanf("%d", &keyToSearch);

    // Call function to search first element by key
    index = search(keyToSearch);
    
    // Element found in the list
    if (index >= 0)
        printf("%d found in the list at position %d\n", keyToSearch, index + 1);
    else
        printf("%d not found in the list.\n", keyToSearch);
    

    return 0;
}

/**
 * Create a list of n nodes
 */
void createList(int n)
{
    struct node *newNode, *temp;
    int data, i;

    head = malloc(sizeof(struct node));

    /*
     * Unable to allocate memory, hence exit from app.
     */
    if (head == NULL)
    {
        printf("Unable to allocate memory. Exiting from app.");
        exit(0);
    }
    

    /* Input head node data from user */
    printf("Enter data of node 1: ");
    scanf("%d", &data);

    head->data = data; // Link data field with data
    head->next = NULL; // Link address field to NULL

    temp = head;

    /*
     * Create n nodes and add to the list
     */
    for (i = 2; i <= n; i++)
    {
        newNode = malloc(sizeof(struct node));

        /* If memory is not allocated for newNode */
        if (newNode == NULL)
        {
            printf("Unable to allocate memory. Exiting from app.");
            exit(0);
        }

        printf("Enter data of node %d: ", i);
        scanf("%d", &data);

        newNode->data = data; // Link data field of newNode
        newNode->next = NULL; // The newNode should point to nothing

        temp->next = newNode; // Link previous node i.e. temp to the newNode
        temp = temp->next;
    }
    
}


/**
 * Display entire list
 */
void displayList()
{
    struct node *temp;

    /*
     * If the list is empty i.e. head = NULL,
     * dont perform any action and return.
     */
    if (head == NULL)
    {
        printf("List is empty.\n");
        return;
    }
    
    temp = head;
    while (temp != NULL)
    {
        printf("%d, ", temp->data);
        temp = temp->next;  // Move to next node
    }
    printf("\n");
}


/**
 * Search an element with given key in linked list.
 * It return a positive integer specifying index of the element 
 * on success, otherwise returns -1.
 */
int search(int key)
{
    int index;
    struct node *curNode;

    index = 0;
    curNode = head;

    // Iterate till last element until key is not found
    while (curNode != NULL && curNode->data != key)
    {
        index++;
        curNode = curNode->next;
    }


    return (curNode != NULL) ? index : -1;
}

You can also write the above search logic using recursive function. But, before you must have at-least basic knowledge of recursion and how to solve problems using recursive function.

Read more: Recursive function exercises and solutions in C.

How to search an element in linked list using recursion?

Before writing recursive search function. Let us first define our recursive function.

int searchRecursive(int key, struct node *curNode, int index);

Our recursive function return index of element if found in linked list otherwise returns -1. It accepts three parameters
key element to search in the linked list.
curNode pointer to current node to check for element.
index current element index.

Let us define our recursive search base conditions.

  1. If curNode == NULL, means no more element to search further and should return -1.
  2. If curNode->data == key, element found hence return current index.
  3. None of the above two conditions satisfies, then move curNode to next node, increment index and make recursive call to search further. Say searchRecursive(key, curNode->next, index + 1);.

Program to search an element in linked list using recursion

/**
 * C program to search an element recursively in Singly Linked List.
 */
#include <stdio.h>
#include <stdlib.h>

/* Node structure */
struct node
{
    int data;          // Data
    struct node *next; // Address
} * head;


/* Function declaration */
void createList(int n);
void displayList();
int  searchRecursive(int key, struct node *curNode, int index);


int main()
{
    int n, keyToSearch, index;

    // Input node count to create
    printf("Enter number of node to create: ");
    scanf("%d", &n);

    createList(n);

    // Display list
    printf("\nData in list: \n");
    displayList();

    // Input element to search from user.
    printf("\nEnter element to search: ");
    scanf("%d", &keyToSearch);

    // Call function to search first element by key
    index = searchRecursive(keyToSearch, head, 0);

    // Element found in the list
    if (index >= 0)
        printf("%d found in the list at position %d\n", keyToSearch, index + 1);
    else
        printf("%d not found in the list.\n", keyToSearch);
    

    return 0;
}

/**
 * Create a list of n nodes
 */
void createList(int n)
{
    struct node *newNode, *temp;
    int data, i;

    head = malloc(sizeof(struct node));

    /*
     * Unable to allocate memory, hence exit from app.
     */
    if (head == NULL)
    {
        printf("Unable to allocate memory. Exiting from app.");
        exit(0);
    }
    

    /* Input head node data from user */
    printf("Enter data of node 1: ");
    scanf("%d", &data);

    head->data = data; // Link data field with data
    head->next = NULL; // Link address field to NULL

    temp = head;

    /*
     * Create n nodes and add to the list
     */
    for (i = 2; i <= n; i++)
    {
        newNode = malloc(sizeof(struct node));

        /* If memory is not allocated for newNode */
        if (newNode == NULL)
        {
            printf("Unable to allocate memory. Exiting from app.");
            exit(0);
        }

        printf("Enter data of node %d: ", i);
        scanf("%d", &data);

        newNode->data = data; // Link data field of newNode
        newNode->next = NULL; // The newNode should point to nothing

        temp->next = newNode; // Link previous node i.e. temp to the newNode
        temp = temp->next;
    }
    
}


/**
 * Display entire list
 */
void displayList()
{
    struct node *temp;

    /*
     * If the list is empty i.e. head = NULL,
     * dont perform any action and return.
     */
    if (head == NULL)
    {
        printf("List is empty.\n");
        return;
    }
    
    temp = head;
    while (temp != NULL)
    {
        printf("%d, ", temp->data);
        temp = temp->next;    // Move to next node
    }
    printf("\n");
}


/**
 * Search an element with given key in linked list recursively.
 * It return a positive integer specifying index of the element 
 * on success, otherwise returns -1.
 */
int searchRecursive(int key, struct node *curNode, int index)
{
    if (curNode == NULL)                // Element not found in the list
        return -1;
    else if (curNode->data == key)   // Element found, return index
        return index;
    else                                // Not found, look in next element
        return searchRecursive(key, curNode->next, index + 1);
}
Enter number of node to create: 5
Enter data of node 1: 10
Enter data of node 2: 20
Enter data of node 3: 25
Enter data of node 4: 30
Enter data of node 5: 35

Data in list:
10, 20, 25, 30, 35,

Enter element to search: 20
20 found in the list at position 2