Search an element

In the given linked list, search for a given key ‘k’. If present return true, else false.

Example

Method 1

Time complexity : O(n)

Algorithm

Iterative solution

1. Traverse in the linked list, starting from head.

2. Initialize current = head.

3. Until current not equal to Null,

     a. current->key is equal to key is being searched, return true.
     b. current = current->next

4. If loop reaches the end, return false.

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
    int data;
    struct LLNode* next;
};

/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //If this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        //O(1) constant time
}
 
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<"->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}

bool Search(struct LLNode* head, int k)
{
	// Initialize current
    struct LLNode* current = head;  
    while (current != NULL)
    {
        if (current->data == k)
        {
            return true;
        }
        current = current->next;
    }
    //Reached end
    return false;
}
 
 
//Main function
int main()
{
    struct LLNode* head = NULL;//Initial list has no elements
    insertAtBeginning(&head, 9);
    insertAtBeginning(&head, 8);
    insertAtBeginning(&head, 7);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 5);
    insertAtBeginning(&head, 4);
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 1);           
    
    cout<<"Input linked list is: ";
    display(&head);
    int k;
    cout<<"Enter key to be searched:  ";
    cin>>k;
    if(Search(head,k))
    {
    	cout<<"\nYes"<<endl;
    }
	else
	{
		cout<<"\nNo"<<endl;
	}    

    return 0;
}
Try It

Method 2

Time complexity : O(logn)

Algorithm

Recursive solution

We use recursive method here,

a. If head is NULL, return false.

b. If head`s key is same as k, return true.

c. Else, Search(head->next, k).

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
    int data;
    struct LLNode* next;
};

/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //If this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        //O(1) constant time
}
 
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<"->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}

bool Search(struct LLNode* head, int k)
{
    if (head == NULL)
    {
        return false;
    }     
    if(head->data == k)
    {
        return true;
    }
    //Recursion
    return Search(head->next, k);	
}
 
 
//Main function
int main()
{
    struct LLNode* head = NULL;//Initial list has no elements
    insertAtBeginning(&head, 9);
    insertAtBeginning(&head, 8);
    insertAtBeginning(&head, 7);
    insertAtBeginning(&head, 6);
    insertAtBeginning(&head, 5);
    insertAtBeginning(&head, 4);
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 1);           
    
    cout<<"Input linked list is: ";
    display(&head);
    int k;
    cout<<"Enter key to be searched:  ";
    cin>>k;
    if(Search(head,k))
    {
    	cout<<"\nYes"<<endl;
    }
	else
	{
		cout<<"\nNo"<<endl;
	}    

    return 0;
}
Try It

 


Next > < Prev
Scroll to Top