O'Reilly logo

A Common-Sense Guide to Data Structures and Algorithms by Jay Wengrow

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required