Build Your Own Growing List

The plan

We want a list we can keep adding to. Idea: keep an array with some spare room plus a counter size that says how many slots are really used. When the array is full, make one twice as big and copy.

class MyList {
    private int[] data = new int[2];   // start small
    private int size = 0;              // how many slots are used
    int copies = 0;                    // just to watch the work

    void add(int value) {
        if (size == data.length) {     // full: grow
            int[] bigger = new int[data.length * 2];
            for (int i = 0; i < size; i++) {
                bigger[i] = data[i];
                copies++;
            }
            data = bigger;
            System.out.println("  grew to " + data.length + " slots");
        }
        data[size] = value;
        size++;
    }

    int get(int index) {
        return data[index];
    }

    int size() {
        return size;
    }
}

public class Main {
    public static void main(String[] args) {
        MyList list = new MyList();
        for (int i = 1; i <= 9; i++) {
            System.out.println("add " + i * 10);
            list.add(i * 10);
        }
        System.out.println("size " + list.size() + ", item 4 is " + list.get(4));
        System.out.println("items copied while growing: " + list.copies);
    }
}

Output

add 10
add 20
add 30
  grew to 4 slots
add 40
add 50
  grew to 8 slots
add 60
add 70
add 80
add 90
  grew to 16 slots
size 9, item 4 is 50
items copied while growing: 14

Why doubling is clever

Growing happened only 3 times for 9 items, and only 14 items were ever copied. Because the array doubles, the copies add up to less than 2 per item in total. So on average each add is O(1) – even though one unlucky add now and then costs O(n).

Think of it like this: Moving to a bigger house: it's a lot of work on moving day, but if each new house is twice as big you move very rarely. Averaged over all the years, the moving work per year is small.

Tip: Java's real ArrayList works exactly like this (it grows by 1.5 times instead of 2). You've just built the most used data structure in Java!