Solution: Designing the Implementation

We have the MaxList ADT and a full test suite for it. Before we write an implementation, let’s think through the design. There are two options, the two we have used for a list ADT: a linked list implementation and an array-backed implementation. We will analyze how each performs across every operation, then pick one.

Linked-list-based MaxList

Before adding anything to the node, notice we can already answer getMax(index) with no extra fields at all: traverse from the head to that index, keeping the largest value seen along the way. That is one traversal, $O (n)$ , and it stores nothing beyond the list itself. The question is whether another design can do better.

Let’s try caching the “maximum so far” in each node so we do not recompute it every time.

To keep track of the maximum so far, we add another field to each node, pointing at the node that holds the maximum value so far.

private static class Node {
  Integer value;
  Node next;
  Node prev;
  Node maxPointer;  // points to the node with the maximum value so far

  // Constructor and other methods omitted for brevity
}

The new field does not change get, contains, indexOf, or size. They cost what they cost on an ordinary linked list: $O (n)$ for the first three, and $O (1)$ for size. The operations to analyze are the ones that must keep maxPointer correct: add, remove, set, and getMax itself.

add(element)

We add a new node at the end of the list. With a tail pointer, this is $O (1)$ .

We also need to set the maxPointer of the new node. If the list was empty, the new node is the maximum so far, so its maxPointer points to itself. Otherwise, the old last node’s maxPointer leads to the maximum so far, and we compare that value with the new element. If the new element is greater, the new node’s maxPointer points to itself; otherwise, it points to the same node as the old last node’s maxPointer. This is a constant number of comparisons and pointer updates.

So the total time for add is $O (1)$ .

remove(element)

Finding the node is $O (n)$ and unlinking it is $O (1)$ , as on any linked list.

After removing a node, the maxPointer values for later nodes may no longer be correct, especially if the removed node was the maximum for some prefix. We can repair them by traversing from the node after the removed one to the end, carrying forward the maximum from the previous node when there is one. This takes $O (n)$ time in the worst case.

So the total time for remove is $O (n)$ .

set(index, element)

Reaching the node at index takes a traversal, which is $O (n)$ . Updating its value field is $O (1)$ .

However, changing one value can affect the maxPointer of this node and of all subsequent nodes. This is true when the new value is larger than before, but also when the old value used to be the maximum and the new value is smaller. To be safe, we repair the maxPointer values from the updated node to the end, the same way as in remove.

So the total time for set is $O (n)$ .

getMax(index)

Reaching the node at index takes a traversal, which is $O (n)$ . Once we are there, following its maxPointer gives the maximum in $O (1)$ .

So the total time for getMax is $O (n)$ , the same as the plain traversal we started with. The maxPointer makes the last step $O (1)$ , but the costly part is reaching the node at index, and on a linked list that takes a traversal no matter what we store in the nodes.

The cache is only worth having if we can also reach position index in $O (1)$ time.

Array-based MaxList

We can implement MaxList using an array, like ArrayList. The main challenge is to support getMax(index) efficiently. If we simply store the elements in an array, we would need to scan the array up to the given index to find the maximum value, which takes $O (n)$ time in the worst case.

To support getMax(index) in $O (1)$ time, we can maintain an additional array that stores the maximum value up to each index.

Consider the example list [5, 7, 3, 8]. We keep the elements in one array and the cumulative maximum in a parallel maxes array:

index       0   1   2   3
          ┌───┬───┬───┬───┐
elements  │░5░│░7░│░3░│ 8 │
          └───┴───┴───┴───┘
          ┌───┬───┬───┬───┐
maxes     │ 5 │ 7 │ 7 │ 8 │
          └───┴───┴───┴───┘
                    ↑
                getMax(2)

Each maxes[i] holds the largest value in the prefix elements[0..i]. The shaded cells above are that prefix for i = 2. So getMax(2) is a single lookup. It reads maxes[2], which is 7, and 7 is the maximum of 5, 7, 3.

As with the linked list, get, contains, indexOf, and size are unchanged. They cost what they cost on an ordinary ArrayList: $O (1)$ for get and size, and $O (n)$ for the two searches. The operations to analyze are again add, remove, set, and getMax.

add(element)

Appending to the end is $O (1)$ amortized, as on any ArrayList. The one difference is that when the array is full, both arrays grow together.

We also need to update maxes. If the list is empty, the new element is the maximum so far. Otherwise, we compare the new element with the current maximum, which is the last entry in maxes, and store the larger one. This takes $O (1)$ time.

So the total time for add is $O (1)$ amortized.

remove(element)

Finding the element and shifting the later elements left is $O (n)$ , as on any ArrayList.

We also need to update maxes after removing an element. This involves recalculating the maximum values from the index of the removed element to the end, which takes $O (n)$ time in the worst case.

So the total time for remove is $O (n)$ .

set(index, element)

Writing the new element at index is $O (1)$ .

As in the linked-list design, the change can affect the maximum at this index and at every later index. We recompute maxes from this index to the end, using the maximum at index - 1 as the starting point when index is not 0. This takes $O (n)$ time in the worst case.

So the total time for set is $O (n)$ . Reaching the element is $O (1)$ here, unlike the linked list, but updating maxes still takes $O (n)$ .

getMax(index)

One lookup in maxes, which is $O (1)$ .

Comparison

Here is a summary of the time complexity for each operation in both implementations:

Operation	Linked-list-based MaxList	Array-based MaxList
`add(element)`	$O (1)$	$O (1)$ amortized
`remove(element)`	$O (n)$	$O (n)$
`set(index, element)`	$O (n)$	$O (n)$
`get(index)`	$O (n)$	$O (1)$
`contains(element)`	$O (n)$	$O (n)$
`indexOf(element)`	$O (n)$	$O (n)$
`size()`	$O (1)$	$O (1)$
`getMax(index)`	$O (n)$	$O (1)$

The only operation where the array-based design is worse is add, and there it is $O (1)$ amortized instead of $O (1)$ worst case. So the array-based design is the better choice.

Implementing it is your exercise

Now you write the implementation. You already have the ADT specification and the test suite from the previous sections. The solution is provided in the code accompanying this chapter.