Aug 102012
 

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.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)