# Search an element

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

### Method 1

Time complexity : O(n)

## Algorithm

Iterative solution

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;
*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
}

//O(1) constant time
}

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
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

int k;
cout<<"Enter key to be searched:  ";
cin>>k;
{
cout<<"\nYes"<<endl;
}
else
{
cout<<"\nNo"<<endl;
}

return 0;
}``````

### 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++ 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;
*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
}

//O(1) constant time
}

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)
{
{
return false;
}
{
return true;
}
//Recursion
}

//Main function
int main()
{
struct LLNode* head = NULL;//Initial list has no elements

int k;
cout<<"Enter key to be searched:  ";
cin>>k;
{
cout<<"\nYes"<<endl;
}
else
{
cout<<"\nNo"<<endl;
}

return 0;
}``````

Scroll to Top