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.
How to search an element in 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.
- Input element to search from user. Store it in some variable say keyToSearch.
- Declare two variable one to store index of found element and other to iterate through list. Say index = 0; and
struct node *curNode = head; - If curNode is not
NULLand its data is not equal to keyToSearch. Then, increment index and move curNode to its next node. - Repeat step 3 till
curNode != NULLand element is not found, otherwise move to 5th step. - 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.
- If
curNode == NULL, means no more element to search further and should return -1. - If
curNode->data == key, element found hence return current index. - 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