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:
|||# rest of code omitted here...|
|||# We begin at the first node of the list:|
|||current_node = first_node|
|||current_index = 0|
|||# If ...|