Searching for an Item

Let’s write contains, which tells us whether a given value is in the list.

public static boolean contains(ListItem head, int target) {
  // TODO
}

This applies the traversal pattern to linear search:

public static boolean contains(ListItem head, int target) {
  ListItem current = head;
  while (current != null) {
    if (current.value == target) {
      return true;
    }
    current = current.next;
  }
  return false;
}

The best case is $O (1)$ and the worst case is $O (n)$ , as it is for linear search on an array.

When the array is sorted, we can use binary search to bring the worst case down to $O (lo g n)$ . Can we do the same for a linked list? No, we cannot.

Binary search needs to jump to the middle element, then to the middle of a half, and so on. A linked list cannot jump to the middle; it would have to follow the next references from the head.

If the list stored objects, we would compare with .equals instead of ==, and we would have to decide what it means to search for null.