Searching

As you know, searching means looking for a value within the list and returning its index. We’ve seen that linear search on an array has a speed of O(N), since the computer needs to inspect each value one at a time.

Linked lists also have a search speed of O(N). To search for a value, we need to go through a similar process to the one we did with reading; that is, we begin with the head and follow the links of each node to the next one. Along the way, we inspect each value until we find what we’re looking for.

Code Implementation: Linked List Search

Here’s how we can implement the search operation in Python. We’ll call this method search and pass in the value we’re searching for:

	def search(self, value):
	current_node = self.first_node
	current_index = 0

	while True:
	if current_node.data == value:
	return current_index

	current_node = current_node.next_node

	if not current_node:
	break

	current_index += 1

	return None

We can then search for any value within the list, like so:

list.search("time")

Using this, we would get back the index of where "time" is located within the list. In our example above, this would be 3.

As you can see, the mechanics of searching are similar to reading. The main difference is that the loop doesn’t stop at a particular index but runs until we either find the value or reach the end of the list.