Challenge 2: Search in a Singly Linked List

Problem statement

It is time to figure out how to implement another favorite linked list function: Search.

To search for a specific value in a linked list, you only have one approach; traverse the whole list until you find the desired value.

In that sense, the search operation in linked lists is similar to the linear search in normal arrays. All of them take O(n) amount of time.

The search algorithm in a linked list can be generalized to the following steps:

1. Start from the head node.
2. Traverse the list until you either find a node with the given value or you reach the end node, which will indicate that the given node does not exist in the list.

Input

The input is a value to be searched.

Output

true if the value is found but false otherwise.

Sample input

Linkedlist = 5->90->10->4 
Value = 4

Sample output

True

Coding exercise

If you know how to insert an element in a list, then searching for an item will not be that difficult for you.

Now based on the steps mentioned above, we have designed a simple coding exercise for your practice.

The Node and LinkedList classes implemented in the previous lessons are available to you.

Test your code against our cases, and see if you can pass them. You have access to IsEmpty(), GetHead(),
PrintList(), InsertAtHead() and InsertAtTail() functions of LinkedList.

Try to solve this exercise on your own. There are hints to help you along the way.

If you get stuck, you can always refer to the solution explained in the next lesson.