Searching the List

Let’s start with the indexOf method. It implements linear search over the nodes of the list.

public int indexOf(T value) {
  Node<T> current = head;
  int index = 0;
  while (current != null) {
    if (Objects.equals(current.value, value)) {
      return index;
    }
    current = current.next;
    index++;
  }
  return -1;
}

The comparison is Objects.equals(current.value, value), not current.value == value. This is the same choice we made in DynamicArray, now that our values are objects of type T rather than ints.

Now we can implement contains by calling indexOf and checking whether the result is -1:

public boolean contains(T value) {
  return indexOf(value) != -1;
}

indexOf is $O(n)$, and so is contains, in the worst case.