Demo: building MyArrayList and watching it resize

Written Explanation

Step 1: the skeleton

Start with the two pieces of state and a small initial capacity, so that resizing happens quickly and is easy to watch.

import java.util.Arrays;

public class MyArrayList<T> {
    private Object[] data = new Object[2];   // capacity 2
    private int size;                         // items stored
    static int resizes;                       // for the demo only
}

The array is Object[], not T[]. Java does not let you write new T[...], because the type T is erased at runtime (the "trying new T()" family of problems from the generics module). The usual workaround is an Object[] and a cast when reading. The cast is safe here because only add(T) ever stores into the array. The compiler cannot prove it, so it reports an unchecked warning, and we silence that on the exact methods with @SuppressWarnings("unchecked").

Step 2: add and get

// O(1) amortized
public void add(T item) {
    if (size == data.length) {
        data = Arrays.copyOf(data, data.length + 1);   // PLANNED MISTAKE
        resizes++;
    }
    data[size++] = item;
}

// O(1)
@SuppressWarnings("unchecked")
public T get(int index) {
    check(index);
    return (T) data[index];
}

private void check(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("index " + index + ", size " + size);
}

Important: the bounds check uses size, not data.length. Slots between size and the capacity exist but are not part of the list, so reading them must be an error. get is O(1) because it is Lesson 1's array arithmetic plus a comparison.

Step 3: the planned mistake

Run 20 adds with the +1 rule from capacity 2:

MyArrayList<Integer> list = new MyArrayList<>();
for (int i = 0; i < 20; i++) list.add(i * 10);
System.out.println("size=" + list.size() + ", resizes=" + resizes);

Real output with data.length + 1:

size=20, resizes=18

Eighteen copies for twenty items. Every add after the second found the array full and copied everything. With 20 items that is not noticeable; with a million it would be catastrophic, because the total copying grows as n², as in Lesson 2.

Step 4: the fix, doubling

Change one expression:

data = Arrays.copyOf(data, data.length * 2);
System.out.println("resized to " + data.length);
resizes++;

Real output for the same 20 adds:

resized to 4
resized to 8
resized to 16
resized to 32
size=20, resizes=4

Four resizes instead of eighteen, at capacities 4, 8, 16, 32. Capacity 32 for 20 items is the cost of the space trade-off: twelve spare lockers. Also note why the copy count here is 4: the resizes happen when adding items 3, 5, 9, and 17.

Step 5: remove, size, and cleaning up

// O(n)
@SuppressWarnings("unchecked")
public T remove(int index) {
    check(index);
    T old = (T) data[index];
    for (int i = index; i < size - 1; i++) {
        data[i] = data[i + 1];       // shift left
    }
    data[--size] = null;             // clear the freed slot
    return old;
}

// O(1)
public int size() { return size; }

Two details. First, shifting starts at index and moves forward, copying each item one place left; going backward would overwrite items you still need (Lesson 1, Mistake 3). Second, data[--size] = null does two jobs: it reduces size and clears the slot that is now spare. Without clearing, the array would still hold a reference to the last item, and the garbage collector could not reclaim it, a small memory leak. Using --size (decrement first) gives the index of the last stored item.

Step 6: write down the costs

In the lab you place these as comments above each method. Keep them honest: "amortized" is only for add, and the removal cost is O(n) in general, though removing the last item shifts nothing.