Search an element in Linked List

By Astha Awasthi

In this C++ tutorial, we are going to discuss how to search an element in a singly Linked list in C++.

What is Linked List?

Linked list is a linear data structure in which elements are linked using pointers. Unlike arrays, elements are not stored in a contiguous memory location. The front node is known as head node and next of last node is null. To traverse a singly linked list we have to traverse from his head.

• Size of linked list is not fixed like but size of arrays are fixed.
• Dynamic memory allocation is there in linked list, so there is no memory wastage in Linked list.
• Inserting a new element is easy it takes place in O(1) time complexity.
• Accessing an element in linked list is costly while in arrays it takes place in O(1) time complexity.
• Each node in a linked list consisting of some data and a pointer(reference) to the next node.

Algorithm:-

• In linked list a node consists of data and pointer (reference ) to next node, So we declare a class Node which kept data of integer type and a pointer next of class type as data members.
• Take a node as head and define it null initially.
• Now push the values to list using reference to head node.
• Take a newnode and allocate it more through the heap using new node(), and its next should refer to head and current will now become head. So, each time when a newnode is pushed in front it will be head.
• Now, to search the key value take a reference node as current node and start it from the head node, if current node -> data is equal to key then print yes otherwise move current to current->next until we do not reach the end of the list means current->next == NULL.

C++ code implementation to search an element in Linked List

#include<bits/stdc++.h>
using namespace std;

 class Node
 {
     public:
      
       int key;
        Node* next;
 };
 
 void push(Node** head, int value)
 {
     Node* newnode= new Node();
     
     newnode->key=value;
     
     newnode->next=*head;
     
     *head=newnode;
 }
 
 bool search(Node*head, int key)
 {
     Node* current=head;
     
      while(current!=NULL)
      {
          if(current->key==key)
          {
              return true;
          }
          
          current=current->next;
      }
      
      return false;
 }
 
 int main()
 {
     Node* head=NULL;
     
     int key;
     
      cout<<"Enter the key value :"<<endl;
       cin>>key;
       
        push(&head,21);
        push(&head,32);
        push(&head,45);
        push(&head,56);
        
        search(head,key)?cout<<"Yes":cout<<"No";
 }

OUTPUT

Enter the key value : 32

Yes

Best Case :- O(1) if head is the key value

Worst Case :- O(n) if key not found or last element is the key value.

Now, we will discuss how to search an element in a linked list using STL

How to declare a linked list in STL?

Syntax:         list<data_type>list_name;

How to push an element in linked list using STL?

Syntax:-        list_name.push_back( value );

How to get the front element of linked list using STL?

Syntax:-         list_name.front();

How to pop the front element from the linked list using STL?

Syntax:-         list_name.pop_front();

Algorithm:-

1. Push the elements in the linked list using list_name.push_back().
2. Now, check all the elements in the linked until linked list not becomes empty, list_name.empty() returns 1 if linked list becomes empty otherwise 0.
3. Get the front element of the linked list using list_name.front() and check if this element is equal to key if yes then print yes on the flag and break the loop, if no the pop the front element using list_name.pop_front().
4. Keep checking until list not become empty if the flag remains off means key is not found in linked list print No.

C++ Code implementation to search an element in linked list using STL

#include<bits/stdc++.h>
using namespace std;

 int main()
 {
     list<int>l;
     
     int key;
     
     l.push_back(1);
     l.push_back(2);
     l.push_back(3);
     l.push_back(4);
     
     cout<<"Enter the key to be searched:"<<endl;
      cin>>key;
     
     int f=0,x;
     
     while(!l.empty())
     {
         x=l.front();
         
         if(x==key)
         {
             cout<<"YES";
              f=1;
              break;
         }
         
         l.pop_front();
     }
     
     if(f==0)
     cout<<"No";
 }

OUTPUT

Enter the key to be searched: 6

No