Problem: A DynamicArray That Shrinks

DynamicArray grows and never shrinks. Add a million elements and then remove them all, and the backing array still has room for a million. The memory is not released until the whole object is garbage collected.

To study shrinking we need a cheap way to remove. The remove(int value) from the first chapter shifts every element after the removed one, so it is $O(n)$ on its own, and that cost would dominate the cost of shrinking. Use removeLast instead. It removes and returns the last element. That is add in reverse. It reads one slot, changes size by one, and does not shift anything.

Here is the outline of the class you are extending, with grow as the chapter analyzed it. The constructor in the first chapter wrote new int[10]. For this exercise, use a starting capacity of $8$, named MIN_CAPACITY, because shrink will need to compare against it. RESIZE_FACTOR = 2 tells grow to double the capacity:

public class DynamicArray {
  private static final int MIN_CAPACITY = 8;
  // grow multiplies the capacity by this
  private static final int RESIZE_FACTOR = 2;

  private int[] arr;
  private int size;

  public DynamicArray() {
    arr = new int[MIN_CAPACITY];
    size = 0;
  }

  public void add(int value) { ... }   // calls grow() when size == arr.length
  private void grow() { ... }          // multiplies capacity by RESIZE_FACTOR, copies size elements

  public int removeLast() { ... }      // you write this
  private void shrink() { ... }        // and this
}

The chapter’s argument that add is $O(1)$ amortized depended on one fact: after each grow, there is a long run of cheap adds before the next grow. Does that still hold when a shrink can happen too?