C++ program to search an element in the linked list

Algorithm for searching an element in linked list in c++

How to search an element in Singly Linked List in C++?

Searching an element in linked list can be simplified as finding if the element is present in the linked list or not. To check if the item is present in the list or not we need to iterate through the whole list and have to check if the iterated element is equal to the item we need to search. In this article we will learn how to write a C++ program to search an element in the linked list. This article also consists of steps and algorithm for the same.

Steps to write a  program to search an element in linked list in C++

These steps are followed if we want to search an element in the linked list.

  1. Define syntax to create linked list.
  2. Initialize the variables.
  3. Create a function named makeList() to create the linked list.
  4. Now create a function to display list that will be used to print the list when required.
  5. Now create a search function to search the element.
  6. If element is present in the linked list print element found
  7. Else print element is not present in the list.

How to define a linked list?

class Node  

    int data; 
    Node *next; 
}; 

Following set of code is used to define a linked list in our program.

C++ program to search an element in the linked list

Algorithm to search an element in linked list

Following algorithm is followed for searching an element in the linked list.

  • IF STNODE==NULL
  • EXIT
  • ElSE WHILE(TMP!=NULL)
  • If TMP-> NUM== ITEM
  • RETURN PRESENT
  • ELSE IF FLAG==N
  • RETURN NOT PRESENT

C++ Program to search element in Linked List

#include <iostream>
using namespace std;

struct node 
{
    int num;                
    node *nextptr;             
}*stnode; //node defined

void makeList(int n);                 
void showList();
void searchList(int item, int n);
 
int main()
{
    int n,num,item;
		
    cout<<"Enter the number of nodes: ";
    cin>>n;
    makeList(n);
    cout<<"\nLinked list data: \n";		
    showList();
    cout<<"\nEnter element you want to search: ";   
    cin>>item;
    searchList(item,n);

    return 0;
}
void makeList(int n) //function to create linked list.
{
    struct node *frntNode, *tmp;
    int num, i;
 
    stnode = (struct node *)malloc(sizeof(struct node));
    if(stnode == NULL)        
    {
        cout<<" Memory can not be allocated";
    }
    else
    {
                                  
        cout<<"Enter the data for node 1: ";
        cin>>num;
        stnode-> num = num;      
        stnode-> nextptr = NULL; //Links the address field to NULL
        tmp = stnode;
 
        for(i=2; i<=n; i++)
        {
            frntNode = (struct node *)malloc(sizeof(struct node)); 
 

            if(frntNode == NULL) //If frntnode is null no memory cannot be allotted
            {
                cout<<"Memory can not be allocated";
                break;
            }
            else
            {
                cout<<"Enter the data for node "<<i<<": "; // Entering data in nodes.
                cin>>num;
                frntNode->num = num;         
                frntNode->nextptr = NULL;    
                tmp->nextptr = frntNode;     
                tmp = tmp->nextptr;
            }
        }
    }
} 


void showList() //function to print linked list
{
    struct node *tmp;
    if(stnode == NULL)
    {
        cout<<"No data found in the list";
    }
    else
    {
        tmp = stnode;
        cout<<"Linked List: ";
        while(tmp != NULL)
        {
            cout<<"\t"<num;         
            tmp = tmp->nextptr;         
        }
    }
} 
void searchList(int item , int n) //function to search element in the linked list 
{  
    struct node *tmp;  
    int i=0,flag;  
    tmp = stnode;   
    if(stnode == NULL)  
    {  
        cout<<"\nEmpty List\n";  
    }  
    else  
    {   
        while (tmp!=NULL)  
        {  
            if(tmp->num == item)  //If element is present in the list
            {  
                cout<<"Item found at location: "<<(i+1); flag=0; } else { flag++; } i++; tmp = tmp -> nextptr;  
        }  
        if(flag==n) //If element is not present in the list
        {  
            cout<<"Item not found\n";  
        }  
    }  
}
Output:
Enter the number of nodes: 5
Enter the data for node 1: 41
Enter the data for node 2: 25
Enter the data for node 3: 36
Enter the data for node 4: 96
Enter the data for node 5: 58

Linked list data: 
Linked List: 	41	25	36	96	58
Enter element you want to search: 36
Item found at location: 3
Linear Search
C++Programm for linear search
Binary Search
C++Programming for binary search
Quiz time

Fun Fact

Insertion and deletion operations on linked list are more efficient then array. But searching is more efficient in array as compared to linked list.