A linked list is a fundamental data structure in computer science and a common subject of technical job interview questions and programming challenges. One of the simplest challenges, and a great starting point for learning linked lists, is to search a linked list to see if it contains a given value.
Linear Search of Linked Lists
Unlike arrays, which allow random access to individual items, linked lists are a chain of nodes that have to be traversed one-by-one to see if the list contains a given value. Each node typically contains a value and a pointer to the next node. The one-by-one traversal of nodes to find a value is called linear search and the worst case performance of linear search is O(n). As the number of nodes in the linked list increases so does the worst case performance. As you may expect, linked lists are typically not an ideal data structure for algorithms that repeatedly search a large number of values.
There are different ways to implement linked lists, but fundamentally it comes down to a class or struct typically called a Node that contains a value and a pointer to another Node. For simplicity, here is a sample Node class in Python.
class Node(object):
def __init__(self, value: int, next_node: "Node" = None):
self.value = value
self.next_node = next_node
def __repr__(self):
return "Node <{}>".format(self.value)
We can create a linked list by chaining a number of Nodes together. Here is a linked list in Python that contains the integers 1 through 5.
linked_list = Node(1, Node(2, Node(3, Node(4, Node(5)))))
Once we have the linked list we can pass it to a function that performs linear search to see if it contains a value. For simplicity, the search function will return True if the linked list contains a value or False if it doesn't. The function accepts the head (first Node) of the linked list as well as an integer value to find.
def find(head: Node, value: int) -> bool:
"""Returns True if value in linked list, otherwise False."""
current_node = head
while current_node is not None:
if current_node.value == value:
return True
current_node = current_node.next_node
return False
The linear search algorithm for the linked list visits each Node one-by-one to see if its value is equal to the search value. If the value is found, it returns True. If the linear search algorithm loops through all Node instances in the linked list and comes up empty, it returns False.
The complete solution in Python for finding a value in a linked list using linear search is as follows.
class Node(object):
def __init__(self, value: int, next_node: "Node" = None):
self.value = value
self.next_node = next_node
def __repr__(self):
return "Node <{}>".format(self.value)
def find(head: Node, value: int) -> bool:
"""Returns True if value in linked list, otherwise False."""
current_node = head
while current_node is not None:
if current_node.value == value:
return True
current_node = current_node.next_node
return False
if __name__ == '__main__':
linked_list = Node(1, Node(2, Node(3, Node(4, Node(5)))))
for i in range(1, 6):
assert(find(linked_list, i))
assert(not find(linked_list, 7))
When you run the Python program from the terminal it will create a linked list and perform a series of linear searches on it. If all searches perform appropriately, it will silently quit. If a search performs unexpectedly, it will raise an error.
Conclusion
As mentioned earlier, linked lists are a popular technical interview question and programming challenge. Searching a linked list using linear search is a great way to start learning linked lists. In future tutorials I will explore other basic operations performed on linked lists as well as popular programming challenges.
