Problem: SparseList

In this chapter we built one ADT, List, and gave it two implementations: ArrayList, backed by an array, and LinkedList, backed by linked nodes. The point of an ADT is that different structures can keep the same contract. In this practice problem you will build a third implementation. This one does not store most of its elements at all.

Say we have a list of ten thousand integers that are almost all 0, with only a few non-zero values in it. An ArrayList would store all ten thousand slots, nearly every one holding the same 0. A sparse list picks one default value, here 0. Any position it does not explicitly store counts as that default. So it only keeps the positions that differ from the default.

Here is a SparseList of length 8 with default 0. Its only non-default values are 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

The list stores just those two positions, as a small linked list of (index, value) nodes, in order of index:

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

Everything else is implied. get(4) finds no node for index 4 and returns the default 0. get(3) finds the node (3, 5) and returns 5.

SparseList will implement the same List<T> interface as ArrayList and LinkedList, with the same operations and the same contract. But it stores its data differently, and its costs are different. An ArrayList uses memory for every position, and in exchange it gets fast indexed access. A SparseList uses almost no memory when the data is mostly uniform, but every access has to traverse the linked list. Which one you want depends on the data you expect to hold.

To keep the focus on the sparse structure itself, we will build only these operations:

  • add(value): append a value at the next position, growing the list.
  • get(index): return the value at a position, or the default if nothing is stored there.
  • set(index, value): change the value at a position, adding, updating, or removing a node as needed.
  • size(): report the list’s length.

The remaining List operations (remove, contains, indexOf) follow the same patterns and are included in the solution that accompanies this chapter.