Getting an Item by Index

Let’s write an operation called get that returns the value at a given index.

public static int get(ListItem head, int index) {
  // TODO
}

As before, we cannot index directly into the list. We follow next references from the head, index times, to reach the item at that position.

public static int get(ListItem head, int index) {
  ListItem current = head;
  for (int i = 0; i < index; i++) {
    current = current.next;
  }
  return current.value;
}

This is the traversal pattern again. Instead of following references all the way to null, we take a fixed number of steps to reach the item at position index.

If this were an array, we would simply access the element at that index and return it. For an array, get is $O(1)$. For a linked list, get is $O(n)$ since we have to follow the references one by one.

What happens if we try to access an index that is out of bounds?

If we pass an index that is too large, current becomes null. Trying to access current.next inside the loop or current.value afterward then throws a NullPointerException. If we pass a negative index, the loop never runs and we try to return current.value when current is still the head. If the list is empty, head is null, so we get a NullPointerException there too. If the list is not empty, we return the head’s value, which is not what we want.

Notice that a NullPointerException does not tell the client that the index was out of bounds. We should validate the index instead and throw an IndexOutOfBoundsException. The challenge with doing that here is that we do not know the length of the list (unless we compute it), so we cannot quickly check whether the index is too large.

I will leave this out of our implementation for now. In this chapter, we will assume that the client always passes a valid index. In a later chapter, we will see how to handle invalid indices.