Solution: Fields and Constructor

Before we write any operations, we have to decide what state a SparseList holds.

A node has to store its own position. In an ArrayList, a value’s position is its slot number, which the array knows implicitly. In a LinkedList, a value’s position is how far down the linked list it is, again implicit. But a SparseList skips the positions it does not store, so a node’s position cannot be recovered from its place in the linked list. Each node must store its own index.

Solution

public class SparseList<T> implements List<T> {

  private Node<T> head;  // front sentinel; the real nodes follow it
  private T defaultValue;  // the value assumed at any position we do not store
  private int size;  // the logical length of the list

  private static class Node<T> {
    int index;  // the position this value occupies in the list
    T value;  // the non-default value stored at that position
    Node<T> next;

    Node(int index, T value) {
      this.index = index;
      this.value = value;
    }
  }

  public SparseList(T defaultValue) {
    this.defaultValue = defaultValue;
    this.head = new Node<>(-1, null);  // sentinel: not a real position
    this.size = 0;
  }

  public int size() {
    return size;
  }
}

We use a front sentinel, the same technique as in the chapter. Here we only need one sentinel, at the front, and the nodes are singly linked. The linked list only ever needs to be traversed forward. The sentinel holds index -1, which is not a real position, so it can never be mistaken for stored data. It guarantees that every real node has a node before it, so set does not have to special-case the front of the linked list. An empty list is the sentinel with a next of null:

         ┌─────┐
head ──▶ │ ░░░ │ ──▶ null
         └─────┘
        sentinel

The defaultValue is fixed when the list is created. ArrayList and LinkedList need no information about their contents when they are created. A SparseList is different: it has to be given the value to assume for every position it does not store.

Finally, size is the logical length of the list, not the number of stored nodes. It is how many positions the list has, including all the default ones. The list of length 8 from the overview has size 8 but only two nodes:

         ┌─────┐     ┌────────┐     ┌────────┐
head ──▶ │ ░░░ │ ──▶ │ (3, 5) │ ──▶ │ (7, 2) │ ──▶ null
         └─────┘     └────────┘     └────────┘
        sentinel

We keep the nodes in increasing order of index. We could instead leave them unsorted, dropping each new node at the front. But then every operation would have to examine every node. A get(i) could never stop early, because index i might be recorded in any node, so we would have to check all of them before concluding it is absent and returning the default. And set would have no particular place to put a new node, since any position in an unordered linked list would do. Keeping the nodes sorted by index fixes both: get can stop as soon as it reaches a node whose index is greater than i, and set and add know exactly where a node belongs. That order is an invariant, and the operations that follow rely on it.