ArrayList

Think of a train. The coaches are hooked together in a row, and each has a number painted on it: coach 0 right behind the engine, then 1, 2, 3. If you want coach 7, you don't walk through coaches 0 to 6 first. You know where seven is, so you go straight there. When the railway needs a longer train, it hooks on more coaches at the back.

That is an ArrayList. It is a List that keeps its items side by side in a row, each with a number called its index. Index 0 is the first item. You can jump to any index at once, and you can keep adding items at the end without ever saying how many you expect.

An ArrayList is the collection you will use most often in Java. If a problem says "a list of things" and nothing else, this is the one to reach for.

Remember: ArrayList is a row with numbered slots. Jumping to a number is instant. Squeezing something into the middle is the part that costs.

Inside every ArrayList is a plain Java array, a fixed row of slots. The picture shows four coaches on a ten-slot array. Two numbers describe it.

• size is how many items are really in the list. Here it is 4.
• capacity is how many slots the array has. Here it is 10.

The six empty slots are room to grow into. Adding to the end writes into the next empty slot, which is quick. An array can't stretch, so when all the slots are full and you add one more, the list must do something clever. It makes a bigger array, copies every item across, and carries on with the new one. You never see this happen. You only see size() go up.

Why not make the array one slot bigger each time? Because then every add would copy everything, and a list of a million items would copy a million items a million times. By making the array noticeably bigger each time it fills, the copying becomes rare, and adding stays cheap on average.

The basics first. Every block below can be pasted into jshell.

List<String> coaches = new ArrayList<>();
coaches.add("Engine");
coaches.add("Chair car");
coaches.add("Pantry");
coaches.set(1, "Sleeper"); // set replaces a slot; it does not insert
System.out.println(coaches);
System.out.println(coaches.get(2));
System.out.println(coaches.indexOf("Pantry"));
System.out.println(coaches.contains("Guard"));

[Engine, Sleeper, Pantry]
Pantry
2
false

add puts a new item at the end. set(1, "Sleeper") replaces what was in slot 1, so the list stays the same length. get(2) reads slot 2. indexOf tells you the position of an item, or -1 if it isn't there. contains just answers yes or no.

Putting an item into the middle uses add with an index, and taking one out uses remove.

// List.of builds a list that cannot change, so copy it into an
// ArrayList when you want one you can add to and remove from.
List<String> line = new ArrayList<>(List.of("A", "B", "C", "D"));
line.add(1, "NEW"); // everything from index 1 moves one place right
System.out.println(line);
line.remove(0); // by index
line.remove("C"); // by value
System.out.println(line);

[A, NEW, B, C, D]
[NEW, B, D]

add(1, "NEW") pushed B, C and D one place along to make room. remove(0) took out the first item by its index, and remove("C") took out an item by its value. Note the new ArrayList<>(List.of(...)) on the first line. List.of builds a list that can't be changed, so we copy it into a real ArrayList first.

Now the trap. What does remove do when your list holds Integers?

List<Integer> nums = new ArrayList<>(List.of(10, 20, 30, 1));
nums.remove(1); // an int: this means "remove the item at index 1"
nums.remove(Integer.valueOf(1)); // an Integer: this means "remove the value 1"
System.out.println(nums);

[10, 30]

There are two methods called remove. remove(int index) removes by position. remove(Object value) removes by value. When you pass a plain int, Java picks the first one: nums.remove(1) removed the item at index 1, which was 20, not the value 1. To remove the value, you have to hand over an Integer object, as in Integer.valueOf(1). In a list of strings you would never notice, which is why this one catches people out in tests.

What if the index is too big?

List<String> coaches = new ArrayList<>(List.of("Engine", "Sleeper", "Pantry"));
try {
    coaches.get(5);
} catch (IndexOutOfBoundsException e) {
    System.out.println(e.getMessage());
}

Index 5 out of bounds for length 3

Asking for a slot that doesn't exist throws an IndexOutOfBoundsException. The message says which index you asked for and how long the list was, which is usually enough to find the bug. The valid indexes are 0 up to size() - 1.

A hint about size. If you know roughly how many items you will add, say so when you create the list:

// A hint that we expect about 1000 items, so the array is made big once.
List<Integer> big = new ArrayList<>(1000);
System.out.println(big.size()); // still empty: the hint is room, not items

0

The hint makes the array big enough once, so it never needs to grow while filling. The list is still empty, as size() shows. The hint is room, not items.

The best way to understand ArrayList is to build a small one. This TinyList has the three moves that matter: add at the end, insert in the middle, and remove.

static class TinyList<T> {
    private Object[] items = new Object[4];
    private int size = 0;

    int size() {
        return size;
    }

    int capacity() {
        return items.length;
    }

    private void growIfFull() {
        if (size == items.length) {
            // Full: make a bigger array and copy everything over. Growing
            // by a fraction each time, not by one slot, is what keeps add
            // cheap on average.
            items = Arrays.copyOf(items, items.length + items.length / 2 + 1);
        }
    }

    void add(T value) {
        growIfFull();
        items[size] = value;
        size++;
    }

    void add(int index, T value) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index " + index + ", size " + size);
        }
        growIfFull();
        // Slide everything from index onwards one slot right, to open a gap.
        System.arraycopy(items, index, items, index + 1, size - index);
        items[index] = value;
        size++;
    }

    @SuppressWarnings("unchecked") // safe: only add can put things in, and it takes a T
    T get(int index) {
        checkIndex(index);
        return (T) items[index];
    }

    @SuppressWarnings("unchecked")
    T remove(int index) {
        checkIndex(index);
        T removed = (T) items[index];
        // Slide everything after the gap one slot left to close it.
        System.arraycopy(items, index + 1, items, index, size - index - 1);
        size--;
        items[size] = null; // let the garbage collector reclaim the old last slot
        return removed;
    }

    private void checkIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index " + index + " out of bounds for length " + size);
        }
    }
}

Go through it in order.

• items is the array, and size counts how many slots are really used. The array starts with 4 slots.
• growIfFull is the clever part. When size has caught up with the array's length, it asks Arrays.copyOf for a bigger copy: the old length plus half of it, plus one.
• add(value) grows if it must, writes the item at slot size, and counts it.
• add(index, value) first opens a gap. System.arraycopy slides everything from index onwards one place to the right, in one fast copy. Then it writes into the gap.
• remove(index) does the reverse. It slides everything after the removed slot one place to the left, then clears the old last slot so the garbage collector (Java's automatic tidier-up of unused objects) can reclaim it.
• get checks the index first, then reads the slot. The cast (T) is safe because only add puts things in, and it only takes a T. That is the one place Java asks us to promise something the compiler can't check, which is why the annotation is there.

TinyList<String> coaches = new TinyList<>();
for (String name : List.of("Engine", "Chair car", "Sleeper", "Pantry", "Guard")) {
    coaches.add(name);
}
System.out.println(coaches.size() + " items, room for " + coaches.capacity());
coaches.add(1, "Dining car");
System.out.println(coaches.get(1) + " then " + coaches.get(2));
System.out.println(coaches.remove(0));

5 items, room for 7
Dining car then Chair car
Engine

Five items didn't fit in four slots, so the array grew from 4 to 7. Then we inserted at index 1 and removed index 0, and the items shifted accordingly.

This picture is the cost of inserting near the front. Everything after the new item has to move one place, and the longer the list, the more there is to move. Reading a slot never moves anything, which is why get is quick.

The real ArrayList works the same way, with a few differences. In OpenJDK, the most widely used Java, an empty ArrayList makes its array only when you add the first item, with room for 10, and each time it fills the array grows by about half again. Those numbers are an implementation detail rather than a promise, so don't write code that depends on them. The promise is only that adding to the end is cheap on average.

Amortised means "averaged over many calls". One add in a long run may copy the whole array, but that is rare enough that the average cost per add stays constant.

Removing from the end is the cheap case (remove(size() - 1) shifts nothing), and removing from the front is the expensive one. If you find yourself removing from the front a lot, you want a different collection. Lesson 9 covers it.

All three use only get, add and size. Notice how each one touches the list, and what that costs.

static <T> List<T> reverseCopy(List<T> items) {
    throw new UnsupportedOperationException("a new list with the items in the opposite order");
}

static <T> List<T> reverseCopy(List<T> items) {
    // Know the final size up front, so the new list never has to grow.
    List<T> result = new ArrayList<>(items.size());
    for (int i = items.size() - 1; i >= 0; i--) {
        result.add(items.get(i));
    }
    return result;
}

static List<Integer> mergeSorted(List<Integer> a, List<Integer> b) {
    throw new UnsupportedOperationException("merge two sorted lists into one sorted list");
}

static List<Integer> mergeSorted(List<Integer> a, List<Integer> b) {
    List<Integer> merged = new ArrayList<>(a.size() + b.size());
    int i = 0;
    int j = 0;
    while (i < a.size() && j < b.size()) {
        // Take the smaller front item. <= keeps equal items in their original order.
        if (a.get(i) <= b.get(j)) {
            merged.add(a.get(i));
            i++;
        } else {
            merged.add(b.get(j));
            j++;
        }
    }
    while (i < a.size()) {
        merged.add(a.get(i));
        i++;
    }
    while (j < b.size()) {
        merged.add(b.get(j));
        j++;
    }
    return merged;
}

static void insertSorted(List<Integer> sorted, int value) {
    throw new UnsupportedOperationException("put value in the right place, keeping the list sorted");
}

static void insertSorted(List<Integer> sorted, int value) {
    int at = 0;
    // Walk past everything smaller; the first item that is not smaller marks the spot.
    while (at < sorted.size() && sorted.get(at) < value) {
        at++;
    }
    sorted.add(at, value);
}

ArrayList questions are about cost and about the traps in its methods.

• "ArrayList or LinkedList?" For almost every job, ArrayList. Jumping to an index is O(1), the items sit side by side in memory, and adding at the end is cheap on average. Lesson 4 explains the rare exceptions.
• "How does an ArrayList grow?" It holds an array. When the array is full, it makes a bigger one and copies the items over. In OpenJDK the new array is about half again as big, which makes adding cheap on average, O(1) amortised.
• "What is the difference between size and capacity?" Size is how many items the list holds. Capacity is how many slots the array has. Capacity is always at least size.
• "What does list.remove(1) do on a List<Integer>?" It removes the item at index 1, not the value 1. To remove the value you pass an Integer object, as in Integer.valueOf(1).
• "Why is inserting in the middle slow?" Everything after the spot has to shift one place to make a gap. That is O(n).
• "Is ArrayList thread-safe?" No. If several threads change one list at the same time, it can break. Lesson 12 mentions the concurrent alternatives.
• "What does get(10) do on a list of three?" It throws an IndexOutOfBoundsException.
• Say the cost. "Get is O(1), add at the end is O(1) amortised, and insert or remove in the middle is O(n)" is a complete answer.

Made by VeraStack Labs