Challenge: Search in a Singly Linked List
This lesson explains how searching is done in a singly linked list. There is also a coding exercise to test your concepts.
We'll cover the following
Problem Statement
To search for a specific value in a linked list, there is no other approach but to traverse the whole list until we find the desired value.
In that sense, the search operation in linked lists is similar to the linear search in arrays - all of them take O(n) amount of time.
The search algorithm in a linked list can be generalized to the following steps:
- Start from the
head
Node. - 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 doesn’t exist in the list.
Input
A linked list and an integer to be searched.
Output
true
if the integer is found. false
otherwise.
Sample Input
Linkedlist = 5->90->10->4
integer = 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 are available to you.
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, which is explained in the next lesson.
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.