Solution: Growing the List: add

The last operation grows the list. Like every List, a SparseList starts empty and gets longer one add at a time. The new value goes at the next position, index size, and the list’s logical length grows by one.

What is different for a sparse list is what we store. If the value being added is the default, there is nothing to record: the position is default, and default positions hold no node. Only a non-default value needs a node, and since its index is the largest so far, that node belongs at the end of the linked list.

Solution

public void add(T value) {
  int index = size;
  size++;

  if (Objects.equals(value, defaultValue)) {
    return;  // a default value stores nothing: no node, no work
  }

  Node<T> prev = head;
  while (prev.next != null) {
    prev = prev.next;  // walk to the end of the chain
  }
  prev.next = new Node<>(index, value);
}

The default case is where the savings come from. When the value is the default, add increments size and returns immediately. There is no traversal and no new node. An ArrayList cannot do that. Every add, default or not, uses up a slot.

When the value is not the default, we append a node. The new index is larger than every index already in the linked list, so the node belongs at the end; we traverse to the end and link it on.

Here is how a list builds up. Starting from an empty SparseList<Integer> with default 0, we add 0, 0, 0, 5, 0, 0, 0, 2 in turn. The five default adds each just raise size and store nothing. Only the 5 (at index 3) and the 2 (at index 7) create nodes:

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

The list now has size 8 and exactly two nodes.

A faster append

Appending a non-default value traverses to the end of the linked list each time, which is $O (k)$ in the number of stored nodes. Keeping a tail reference to the last node, as the chapter’s LinkedList did, would make the append $O (1)$ . We are not doing that here. In a list that is mostly default, non-default adds are rare, so the traversal is usually short.

Summary

With add, get, set, and size, the SparseList works as a list. From the outside there is no way to tell it apart from an ArrayList or a LinkedList. The remaining List operations are remove, contains, and indexOf. They follow the same patterns of traversing the linked list, and they are in the solution that accompanies this chapter.

So this is a third implementation of the List ADT. It keeps the exact same contract as ArrayList and LinkedList, so any code written against List will accept it without change. What it stores, and what it costs, are different from both. It can hold a list of a million entries in a small number of nodes, as long as those entries are mostly the same. The cost is a traversal of the linked list on every read and write. The ADT only tells us what a list does, not what it costs. The cost comes from the implementation, and the implementation can be an array, linked nodes, or a sparse linked list. Which one to use depends on the data.