A Common-Sense Guide to Data Structures and Algorithms, Second Edition, 2nd Edition

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 go through a similar process as we did with reading. That is, we begin with the first node 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 Ruby. We’ll call this method index_of, and pass in the value we’re searching for:

def index_of(value)
  # We begin at the first node ...