ArrayList

In the last lesson the list grew by itself, and nobody set its size. But inside an ArrayList there is an ordinary array, and an array cannot grow. So how does it work?

Back to the cloakroom. Hats sit on a shelf with slots. When the free slots run out, the attendant takes a bigger shelf, moves all the hats onto it in order and puts the old one away. ArrayList does the same with its array.

But first, let's see what a list can do:

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> shelf = new ArrayList<>();
        shelf.add("hat");
        shelf.add("scarf");
        shelf.add("gloves");
        shelf.set(1, "cap");
        System.out.println(shelf);                   // [hat, cap, gloves]
        System.out.println(shelf.get(2));            // gloves
        System.out.println(shelf.contains("scarf")); // false
    }
}

Let's go through the program line by line:

1. Three calls to add put "hat", "scarf" and "gloves" at the end of the list in turn. They get the indices 0, 1 and 2.
2. shelf.set(1, "cap") replaces the element at index 1: "cap" takes the place of "scarf".
3. System.out.println(shelf) prints [hat, cap, gloves].
4. shelf.get(2) reads the element at index 2, which is gloves.
5. shelf.contains("scarf") checks whether the list has such an element and answers false: the scarf was already replaced. It compares elements with equals.

An index outside the list stops the program, as it does for an array: shelf.get(3) throws an IndexOutOfBoundsException.

How an ArrayList grows

Inside an ArrayList there is an array. Its length is called the list's capacity, and the number of filled slots is its size. These are different numbers: the array almost always has room to spare.

Here is what happens in JDK 25:

1. new ArrayList<>() does not set aside room for elements yet.
2. The first add creates an array of 10 slots.
3. While there is a free slot, add puts the element into it, and that is fast.
4. When the slots run out, the next add creates a new array about one and a half times longer, copies all the elements into it and adds the new one.

So the capacity grows like this: 10, 15, 22, 33, 49. Copying happens rarely, and on average adding to the end stays fast. How an ArrayList grows is a common interview question.

Inserting at the start or in the middle costs more. add(0, x) puts an element at the start and shifts all the others one slot to the right. remove by index, the other way round, shifts every element after the removed one to the left. In a list of a million elements, that is up to a million moves.

Here the shelf picture is not exact. A real attendant moves the hats in front of everyone, but the variable shelf never notices the move. It still leads to the same ArrayList object, and that object keeps the new array inside itself.

remove by index and by value

A list has two remove methods:

• remove(int index) removes the element at that index;
• remove(Object o) looks for the first element equal to o by equals and removes it.

In a list of strings there is no confusion: shelf.remove("cap") can only mean the second method. But in a List<Integer> both fit, and this is where people slip:

List<Integer> nums = new ArrayList<>();
nums.add(7);
nums.add(5);
nums.add(1);
nums.remove(1);
System.out.println(nums); // [7, 1]
nums.remove(Integer.valueOf(1));
System.out.println(nums); // [7]

Let's look at both calls:

1. In nums.remove(1) the argument is an int. The compiler first looks for a method that fits without autoboxing and finds remove(int index). The element at index 1 is removed, which is 5.
2. Integer.valueOf(1) is already an object, so remove(Object o) is called. It finds the number 1 and removes it.

Common mistake

The number 70 was meant to be removed from a list of scores:

List<Integer> scores = new ArrayList<>();
scores.add(50);
scores.add(70);
scores.add(90);
scores.remove(70); // ✗

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 70 out of bounds for length 3

The program compiles but stops when it runs. Java took 70 as an index, and a list of three has no element at index 70. To remove the value, pass an object: scores.remove(Integer.valueOf(70)).

Key points

• ArrayList keeps elements in an array: add puts one at the end, get and set read and change by index, size and contains tell you about the contents.
• When the array is full, ArrayList creates a new one about one and a half times longer (10, 15, 22, 33…) and copies the elements into it.
• add(0, x) and remove by index shift every element after that spot.
• On a List<Integer>, remove(1) removes the element at index 1, and the number 1 is removed with remove(Integer.valueOf(1)).