Access and Search

Reading and searching the list are both linear traversals. Both start at the first real node, head.next, and stop at the back sentinel, tail.

Let’s implement get:

public T get(int index) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
  }
  Node<T> current = head.next;
  for (int i = 0; i < index; i++) {
    current = current.next;
  }
  return current.value;
}

We have two search methods, indexOf and contains. Let’s start with indexOf:

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

Now we can implement contains in terms of indexOf:

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

Keep in mind that both get and indexOf are written in the simplest way that works. They could be made faster in practice by using some heuristics that take advantage of the list’s sorted order:

When it comes to get, we can start from the closer end. That roughly halves the longest traversal.
When it comes to indexOf, we can stop the search early. Because the list is sorted, we can stop as soon as we reach a value that is greater than the one we are looking for.

Neither refinement changes the asymptotic complexity of the operation.

Binary search can be implemented on a linked list, but without constant-time access to the middle element, it does not give us the $O (lo g n)$ running time we get with an array. In fact, a straightforward implementation using our get(mid) at each step takes $O (n lo g n)$ time in the worst case, which is worse than the $O (n)$ time of linear search.