A Common-Sense Guide to Data Structures and Algorithms

Searching

Arrays and linked lists have the same efficiency for search. Remember, searching is looking for a particular piece of data within the list and getting its index. With both arrays and linked lists, the program needs to start at the first cell and look through each and every cell until it finds the value it’s searching for. In a worst-case scenario—where the value we’re searching for is in the final cell or not in the list altogether—it would take O(N) steps.

Here’s how we’d implement the search operation:

class LinkedList

  attr_accessor :first_node

  # rest of code omitted here...

  def index_of(value)
    # We begin at the first node of the list:
    current_node = first_node
    current_index = 0

    begin
      # If ...