Solution: Two Cursors in Step

We make SparseList iterable by declaring it implements Iterable<T> and adding an iterator() that returns an inner-class iterator:

@Override
public Iterator<T> iterator() {
  return new SparseListIterator();
}

private class SparseListIterator implements Iterator<T> {
  private int cursor = 0;               // next logical position to return
  private Node<T> current = head.next;  // next stored node, or null

  @Override
  public boolean hasNext() {
    return cursor < size;
  }

  @Override
  public T next() {
    if (!hasNext()) {
      throw new NoSuchElementException();
    }
    T value;
    if (current != null && current.index == cursor) {
      value = current.value;   // a node stores this position
      current = current.next;  // consume it
    } else {
      value = defaultValue;    // nothing stored here, so it is the default
    }
    cursor++;
    return value;
  }
}

The cursor is the next logical position to return, and current is the next stored node we have not yet passed, starting at the first real node after the sentinel. hasNext() checks the logical length, cursor < size, not the nodes. There are positions left to report even when no nodes remain, because those positions are all the default.

next() checks whether a node is stored at position cursor. If current is non-null and its index equals cursor, that position has a stored value, so we return it and advance current past that node. Otherwise the position holds the default, and current does not advance until cursor reaches its index. Either way the cursor advances by one. The nodes are kept sorted by index, so current only has to move forward. That keeps current aligned with the cursor for the whole iteration.

Trace it on the length-8 example. Positions 0, 1, and 2 find no matching node and return 0. Position 3 matches (3, 5) and returns 5, and current advances to (7, 2). Positions 4, 5, and 6 return 0. Position 7 matches and returns 2. That is 0 0 0 5 0 0 0 2, the full logical sequence.

As with LinkedSet, the iterator is an inner class. That way it can read the list’s head, size, and defaultValue directly, and it can use the type parameter T.

The fail-fast extension uses the same modCount mechanism as the set iterators. The structural changes to a SparseList are add, remove, and the set calls that insert or drop a node, so those are the methods that increment modCount.