Solution: Reading a Value: get

public T get(int index) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
  }
  Node<T> current = head.next;
  while (current != null && current.index < index) {
    current = current.next;  // skip past earlier positions
  }
  if (current != null && current.index == index) {
    return current.value;  // a value is stored here
  }
  return defaultValue;  // nothing stored here, so it is the default
}

The bounds check comes first, because get promises to throw for an invalid index no matter how the list is stored. Note that the check uses size, the logical length, not the number of nodes: index 4 is valid in our length-8 list even though no node holds it.

The traversal advances only while current.index < index. It stops at the first node whose index is index or greater. The sorted order does not tell us anything more than that. When the loop ends, one of two things is true:

• The node the traversal stops at has the index we want, so we return its stored value.
• It does not (its index is larger, or the traversal reaches the end of the linked list), so nothing is stored at our position, and the answer is the default.

Take the length-8 example with nodes (3, 5) and (7, 2). Say we call get(4). The traversal starts at (3, 5). Since $3<4$, it steps forward to (7, 2):

         ┌─────┐     ┌────────┐     ┌────────┐
head ──▶ │ ░░░ │ ──▶ │ (3, 5) │ ──▶ │ (7, 2) │ ──▶ null
         └─────┘     └────────┘     └────────┘
                                        ▲
                                     current  (index 7 > 4, stop)

Now current.index is 7, which is not 4, so no value is stored at position 4. We return the default, 0. Calling get(3) instead would stop at the first node, find current.index == 3, and return its value 5.