Solution: Writing a Value: set

set is the operation that keeps the list sparse. The representation has one rule: a position has a node if and only if its value differs from the default. Every time we write a value, we have to keep that rule true.

That means set has to answer two questions: is the new value the default or not, and is there already a node at this position? The two questions give four situations:

New value is not the default, and a node already exists → update the node’s value.
New value is not the default, and no node exists → insert a new node.
New value is the default, and a node exists → remove the node (the position goes back to default).
New value is the default, and no node exists → do nothing (it was already default).

Solution

public void set(int index, T value) {
  if (index < 0 || index >= size) {
    throw new IndexOutOfBoundsException();
  }

  Node<T> prev = head;
  Node<T> current = head.next;
  while (current != null && current.index < index) {
    prev = current;
    current = current.next;
  }
  boolean hasNode = (current != null && current.index == index);

  if (Objects.equals(value, defaultValue)) {
    if (hasNode) {
      prev.next = current.next;  // remove the node: position returns to default
    }
    // otherwise it is already the default, so there is nothing to do
  } else {
    if (hasNode) {
      current.value = value;  // a node is already here: just update it
    } else {
      Node<T> node = new Node<>(index, value);
      node.next = current;  // insert the new node between prev and current
      prev.next = node;
    }
  }
}

The traversal is the same one get uses, with one addition: we keep prev, the node just before current, so that we can splice into or out of the linked list. When the loop ends, current is either the node at our index or the first node past it, and prev is the node immediately before that position.

Because prev starts at the sentinel head, it is never null, even when we insert or remove at the very front of the linked list. The line prev.next = ... works whether prev is the sentinel or a real node, so none of the four cases needs a special branch for “first in the linked list.”

Two of the cases change the linked list. Start from our length-8 list with nodes (3, 5) and (7, 2). Calling set(5, 9) writes a non-default value at a position with no node. It traverses to find prev at (3, 5) and current at (7, 2), then splices a new node between them:

         ┌─────┐     ┌────────┐     ┌────────┐     ┌────────┐
head ──▶ │ ░░░ │ ──▶ │ (3, 5) │ ──▶ │ (5, 9) │ ──▶ │ (7, 2) │ ──▶ null
         └─────┘     └────────┘     └────────┘     └────────┘
                                        ▲
                                    new node

Calling set(3, 0) instead writes the default value at a position that does have a node. That removes the node, and position 3 goes back to being a 0 like everything else:

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

In both cases size does not change. Only the number of nodes we store changes. This needs import java.util.Objects; at the top of the file.