Search an element in Linked List

Today we are going to discuss the algorithm to search an element in linked list data structure. But if you do not know what a linked list is then press on the link. Searching is a very basic problem. So let's see how to do search an element in linked list.

Procedure

1. First we will make a linked list.

2. Now we will traverse the linked list.

3. For each node we will compare its data with the value to be searched.

Code

#include<iostream>
using namespace std;
struct node
{
    int data;
    struct node* next;
};
struct node* head=NULL;

class linked
{
public:
    void insert(int x)
    {
        struct node* temp=new node();
        temp->data=x;
        temp->next=NULL;
        if(head==NULL)
        {
            head=temp;
        }
        else
        {
            struct node* temp1=head;
            while(temp1->next!=NULL)
            {
                temp1=temp1->next;
            }
            temp1->next =temp;
        }
    }

    void search(int x)
    {
         int flag=0,c=0;
         struct node* temp=head;
         while(temp!=NULL)
         {
             if(temp->data==x)
             {
                flag=1;
                break;
             }
             temp=temp->next;
             c++;
         }
         if(flag==1)
         {
             cout<<"value found at "<<c+1<<endl;
         }
         else
         {
             cout<<"value not found ";
         }

    }

    void disp()
    {
        struct node* temp=head;
        while(temp!=NULL)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }
        cout<<endl;
    }
};

int main()
{
    linked l;
    l.insert(2);
    l.insert(5);
    l.insert(2);
    l.insert(6);
    l.insert(4);
    l.insert(5);
    l.insert(1);
    l.insert(3);
    l.insert(2);
    l.insert(6);
    l.insert(5);
    l.insert(2);
    l.insert(9);
    l.insert(7);
    l.insert(6);
    l.insert(2);
    l.insert(3);
    l.insert(3);
    l.insert(14);
    l.insert(2);
    l.disp();
    int n;
    cout<<"enter value to be searched: ";
    cin>>n;
    l.search(n);
    return 0;
}

Explanation of code(line by line)

1. First we will write a simple code of linked list which will have 2 functions:

- insert() - which will insert elements in the linked list.
- disp() - which will display the linked list.

2. Insert some values in the linked list.
3. We have made a function named search() in which we will write the algorithm for searching a value. Search() also takes an argument which is the value to be searched in the linked list.
4. We have made 3 variables.
- flag - which will indicate we have found the value to be searched or not. Initial value is 0.
- c - which will count the position of node. Initial value is 0
- temp - which is pointer to node. Initially pointing to head.
5. Next we have started the while loop which will iterate over the linked list.
6. Inside the while loop we have placed an if condition which checks if the data in current node is equal to the value to be searched or not.
7. If the data is equal to value to be searched then we make as flag=1 and break out of the loop.
8. Otherwise we will increment to next node and increment c as well.
9. After the while loop is over then we will check if flag is 1 or 0.
- If flag is 1 then we have found the value. So we display a message along with c+1 which gives the position of that value in the linked list.
- If flag is 0 then that means we have not found the value in the linked list.

Search an element in Linked List

Procedure

Code

Explanation of code(line by line)

Output

Contact Form