Search an element in Linked List
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:-
- Push the elements in the linked list using list_name.push_back().
- 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.
- 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().
- 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
Leave a Reply