Given a singly linked list, write a function which will search for a value in the list. Signature of the function will be as shown below:
bool search(Node*head, int x);
head points to the first Node in the list. The function should return true is x is present in the list as false.
In a linked list only linear search can be made (No-Binary search even if the list is sorted). Hence the solution is simple,
Check each Node of the list,
if value in Node == x
return TRUE
When the list is over return FALSE
Non-Recursive Solution:
bool search(Node* head, int x)
{
for(; head != NULL; head = head->link)
{
if(head->data == x)
return true;
}
return false;
}
Recursive Solution:
Before getting fascinated with recursion, you should know that recursion comes with its side effects
bool search(Node* head, int x)
{
if(head == NULL)
return false;
if(head->data == x)
return true;
search(head->link, x);
}
Time Complexity: O(n) for both recursive & Non-Recursive implementation
Extra Space Used: For Non-Recursive O(1). For Recursive Solution, O(n) (Space used in the stack to store activation records of function getting called recursively.
