Problem: Iterating a SparseList

Recall SparseList from the List ADT chapter’s practice problems. It is a List<T> that picks a default value and stores only the positions whose value is different from the default. It keeps those positions in a linked list of (index, value) nodes, sorted by index, after a sentinel head node. Any position with no node holds the default. Here is a length-8 list with default 0, holding a 5 at index 3 and a 2 at index 7:

index:   0   1   2   3   4   5   6   7
value:   0   0   0   5   0   0   0   2

Internally it stores only the two non-default values:

┌────────┐     ┌────────┐
│ (3, 5) │ ──▶ │ (7, 2) │
└────────┘     └────────┘

Your task is to make SparseList iterable, so it can be used in an enhanced for loop. The loop has to produce the list’s full logical sequence. That is one value for every position from 0 to size - 1, in order. A position with no node produces the default value. For our length-8 list,

for (Integer v : list) {
  System.out.print(v + " ");
}

should print:

0 0 0 5 0 0 0 2

It is tempting to traverse the linked list, but that visits only the stored non-default values, 5 and 2, and skips every default position. Your iterator has to traverse the logical positions instead. The idea is to step an index from 0 to size - 1 and advance a node pointer along the way. At each position, read the value from the matching node if there is one, and use the default if there is not. Your hasNext() and next() do the same thing. The iterator keeps the current position and the node pointer as fields.

Remember the contract: next() throws NoSuchElementException when there are no positions left. As an extension, make the iterator fail-fast. Increment a modCount on every structural change to the list, record it when the iterator is created, and check it in next().