ArrayList: a list that can grow

An array holds a row of values, and you choose its length the moment you create it. That works when you know the count ahead of time. Often you do not: test scores come in one student at a time, songs get added to a playlist, items leave a shopping basket. An ArrayList is a list that grows when you add to it and gets shorter when you take something out. This lesson shows you how to use one, and what it does on the inside.

When an array is the wrong size#

Say you are collecting test scores as students hand in their papers, and you do not know how many students will turn up. An array makes you pick a length on day one. Pick 3, and the fourth paper has nowhere to go.

An array cannot grow, so the only way to fit one more score is to build a bigger array, copy every old score into it, and then store the new one. Step through this and watch the copy happen.

It prints Scores stored: 4 and Newest score: 64. The last step, scores = bigger;, points scoresat the new array so the rest of the program uses it. That is a new array, a loop and a reassignment for every score that arrives, and removing a score would need its own loop to shift the later values left. This chore is so common that Java's library does it for you, in a ready-made tool called ArrayList.

Your first ArrayList#

Here is the same job done with an ArrayList. There is no length to choose. You start with an empty list and add each score when it arrives.

It prints [90, 75, 88, 64], then Number of scores: 4, then First score: 90. Step through it and watch the memory view under the code. The list is drawn as a row of numbered cells that gains a cell with each add, and the narration says what each line did. The faint empty cells after the values are spare room, and the small caption under the row reads size 4, capacity 10. Those spare cells get their own section later on.

Reading the recipe

Three lines in that program are new. Take them one at a time.

• import java.util.ArrayList; sits above the class. ArrayList is not built into the language the way int is. It comes from Java's standard library, the large set of ready-made code that ships with the JDK. The library is sorted into named groups called packages, and ArrayList lives in the one called java.util. The import line tells the compiler where to find it. Leave it out and the compiler stops with cannot find symbol.
• ArrayList<Integer> scores = new ArrayList<>(); declares a variable and gives it a brand-new, empty list. The type is ArrayList<Integer>, an ArrayList that holds Integer values (a little further down you will see why it says Integer and not int). The angle brackets say what goes inside, like a label on a storage box. The word new builds the list. The angle brackets on the right are empty, <>, which tells Java to copy the type from the left so you do not write it twice. People call that empty pair the diamond.
• scores.add(90);asks the list to do something. Read it as “scores, add 90”. The actions a list knows how to do are called its methods, and the dot picks one of them. add puts the value in the parentheses at the end of the list.

Printing a list shows its contents in square brackets, separated by commas. Printing an array does not: System.out.println on an int[] gives something like [I@1b6d3586, a type code and a number instead of the values. scores.size() answers how many values the list holds right now, and scores.get(0) fetches the value at index 0. Indexes count from 0, exactly as they do in an array.

Key idea

An ArrayList is a list that grows. You create it empty with new, say what it holds in the angle brackets, and ask it to add, get or remove values with a dot.

Why Integer and not int

Scores are whole numbers, so you might expect to write ArrayList<int>. The compiler refuses:

The angle brackets only accept object types. int, double, boolean and char are primitive types: plain values, not objects. “Required: reference” is the compiler's way of asking for an object type. So each primitive type has an object partner made for this job, called a wrapper class:

You rarely have to do the wrapping yourself. When you write scores.add(90), Java wraps the int 90 in an Integer for you, which is called autoboxing. When you read a value back into an int variable, as in int first = scores.get(0);, Java unwraps it again, which is called unboxing.

Reading and changing items#

Four methods do most of the everyday work. Each takes an index, counting from 0 like an array.

• get(i) hands back the value at index i.
• set(i, value) replaces the value at index i. The list stays the same size.
• add(i, value) inserts a value at index i. Everything from i onward moves one place right to make room.
• remove(i) takes out the value at index i. Everything after it moves one place left to close the gap.

Step through this playlist and keep an eye on the memory view at each change. After an insert, every later song sits one cell further right, and after a remove, one cell further left.

After playlist.add(1, "Sunrise") the list prints as [Intro, Sunrise, Waves, Echo]: Sunrise slid in at index 1 and pushed Waves and Echo one place right. playlist.set(2, "Tides") overwrote Waves, so the list still holds four songs: [Intro, Sunrise, Tides, Echo]. playlist.remove(0) took Intro out and everything shifted left, giving [Sunrise, Tides, Echo], so the last line prints Now playing: Sunrise.

Asking for an index that is not there

The valid indexes of a list run from 0 to size() - 1, the same rule as an array. Ask for anything outside that range and the program stops.

The program prints Last song: Echo and then stops on the second get. In a terminal, Java reports Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 3 out of bounds for length 3, followed by a few lines starting with at that say where it happened.

Read it the way you learned for arrays. The first number is the index you asked for, and the second is the size of the list (the message calls it length). When the two are equal, you asked for one past the end. An array reports an ArrayIndexOutOfBoundsException, and a list reports the more general IndexOutOfBoundsException, with the same meaning. Inserting past the end fails the same way, worded a little differently: add(9, x) on a two-item list reports Index: 9, Size: 2. Reading the rest of the message is part of reading errors and debugging.

Removing by position or by value#

remove comes in two forms. Give it an index and it removes whatever sits at that position. Give it a value and it searches for that value and removes the first match.

basket.remove("apple") took out only the first apple, leaving [bread, apple, cheese]. basket.remove(2) took out whatever was at index 2, the cheese, leaving [bread, apple]. Removing a value that is not in the list changes nothing, and remove answers false so you can tell: the last line prints Removed jam? false.

With a list of strings, Java tells the two forms apart easily: a number means a position and text means a value. A list of numbers is where it goes wrong. A hotel keeps a list of rooms that still need cleaning, and room 3 has just been cleaned. Predict what this prints before you run it.

It prints [12, 7, 3]. Room 9 vanished and room 3 is still waiting. The call rooms.remove(3) removed index 3, the fourth room in the list, which happened to be room 9.

Why did Java pick the position? ArrayList has two methods named remove: one takes an int index, and the other takes an object to search for. (Two methods sharing a name is called overloading, and you will write your own in the methods lesson.) Your argument, 3, is an int. When Java chooses between methods with the same name, it first looks for one that takes the argument as it is, without wrapping it. remove(int) takes an int as it is, so it wins, and Java never tries wrapping 3 into an Integer.

To remove the value, hand remove an Integer object instead of a plain int. Integer.valueOf(3) gives you one:

Now it prints [12, 7, 9]. An Integer fits remove(Object) as it is, while remove(int) would need it unwrapped first, so this time Java picks the search, finds the value 3 and removes it.

Key idea

remove(i) with an int removes a position. remove(Integer.valueOf(x)) removes a value. On a list of numbers, write the form that says what you mean.

Asking a list questions#

Some methods change nothing. They only answer a question about the list.

• isEmpty() answers true when the list holds nothing. It means the same as size() == 0 and reads better.
• size() is the number of values in the list right now: Items: 3.
• contains(x) answers whether the value is anywhere in the list: true for eggs, false for jam.
• indexOf(x) gives the index of the first match, here 1 for bread, or -1 when there is no match. A real index is never negative, so -1 can safely mean “not found”.
• clear() removes everything at once. The list prints as [] afterwards.

You now know three ways to ask “how many?”, one for each kind of thing. Expect to mix them up a few times; the compiler tells you when you do.

Fixed lists with List.of#

Typing one add per line gets tedious when you already know the values. List.of, added in Java 9, builds a list from its values in a single line. The list it builds can never change, though, and the program below shows what happens when you try.

The first two lines print [Mon, Tue, Wed, Thu, Fri] and 5 school days, starting with Mon. Then days.add("Sat") stops the program with an UnsupportedOperationException. A list made by List.of is unmodifiable: add, set, remove and clear all throw this exception, while reading with get, size and contains works as usual. Notice that the program compiled. The compiler does not know this list is fixed, so the mistake only shows up when the line runs.

The variable's type is List<String>, without “Array” in front. List is the general name for any list. An ArrayList is one kind of List, the fixed list that List.of returns is another kind, and a List variable can hold either. To use the name, import it with import java.util.List;. You will often see real code declare List<Integer> scores = new ArrayList<>(); for this reason. Everything on this page works the same with that declaration, and interfaces explains why programmers like to write it that way.

When you want a list that starts with some values and can still change, hand the fixed list to new ArrayList<>(...). It copies the values into a fresh ArrayList that you are free to change:

That prints [Mon, Tue, Wed, Thu, Fri, Sat]. The rest of this lesson uses this shortcut to keep the examples short.

Walking through a list#

Both loops from the arrays lesson work on a list. The counting loop runs an index from 0 up to size() - 1 and reads each value with get(i). The for-each loop hands you each value in turn and hides the index.

The counting loop prints Student 1: 90, Student 2: 75 and Student 3: 88. It uses scores.size() where an array loop used .length, and scores.get(i) where it used scores[i]. Reach for it when you need the position, here to number the students.

The for-each loop is shorter when you only need the values. Its loop variable is a plain int, and Java unboxes each Integer on the way out. The total is 253, and the last line prints Average: 84.33333333333333. The (double) cast stops integer division from dropping the fraction, as in the arrays lesson.

Removing items while you loop

Say you want to drop every score below 50. The obvious attempt removes them inside a for-each loop. Run it.

Java stops with a ConcurrentModificationException, and it points at the for line, not at the removeline. A for-each loop keeps a bookmark in the list as it walks. Removing 45 shifted the later values left behind the loop's back, so when the loop went to fetch the next value, it saw that the list had changed under it and stopped rather than guess. “Concurrent modification” here means “changed while being walked”. Adding inside a for-each loop fails the same way.

A counting loop does not crash, but it has a quieter bug. Predict what this prints.

It prints [72, 38, 90]. When i was 1, the loop removed 45, and 38 slid left into index 1. Then i++ moved on to index 2, so the loop never looked at 38.

That leaves two safe ways. The first is to walk the list backwards. Removing a value shifts only the values after it, and going backwards you have already checked all of those.

It prints [72, 90]. This time removing by position is exactly what you want: i is an index, so scores.remove(i) removes the value at that position. The second safe way is removeIf, which walks the list and does the removing for you:

It prints [72, 90] too. Read score -> score < 50as “given a score, remove it if it is below 50”. That small rule is called a lambda. For now, copy the shape and change the condition; enums and lambdas explains how it works.

Key idea

Never add to or remove from a list while a for-each loop is walking it. Walk it backwards with an index, or let removeIf do the removing.

1import java.util.ArrayList;
2import java.util.List;
3 
4public class Main {
5    public static void main(String[] args) {
6        ArrayList<Integer> scores = new ArrayList<>(List.of(72, 45, 38, 90, 49, 66));
7 
8        // TODO: remove every score below 50
9 
10        System.out.println(scores);
11    }
12}

Inside an ArrayList: the backing array#

Remember the chore from the start of the lesson: build a bigger array, copy everything across, then store the new value. An ArrayList does exactly that, out of sight. Inside every ArrayList is an ordinary array called its backing array, and the list keeps its values in the first slots of it.

The backing array is usually longer than the list. Its length is the list's capacity, while the number of values actually stored is the size. When you add and a slot is free, the value simply goes into the next free slot. When every slot is taken, the add does three things:

1. 1It makes a new array half as big again: the old length plus half of it, rounded down. 10 slots become 15, 15 become 22, 22 become 33.
2. 2It copies every value from the old array into the new one, in order.
3. 3It stores the new value in the next free slot, and from then on uses only the new array. Nothing points at the old array any more, so Java frees its memory automatically.

A list made with new ArrayList<>() starts with no backing array at all, and the first add makes one with 10 slots. Press the buttons and watch the slots fill. Add values until the array is full, then add one more.

Now watch the real thing. This program adds 16 ticket numbers to an empty list. Step through it and read the narration at the 1st, 11th and 16th add: the list makes its first array, then copies its 10 values into a 15-slot array, then its 15 values into a 22-slot array.

It prints the 16 tickets from 101 to 116 in square brackets, then size: 16. The memory view ends with 16 values and 6 spare slots: size 16, capacity 22.

Removing never makes the backing array smaller. Remove ten values and there are simply ten more spare slots, and even clear() keeps the same array ready for the next round of adds. A list copied from List.of, like the ones earlier in this lesson, starts with exactly as many slots as values, which is why those lists started with no spare slots in the memory view.

Key idea

An ArrayList is an array with spare room. When the room runs out, it makes a new array half as big again, copies everything across and carries on.

Array or ArrayList?#

Both hold a row of values that you reach by index. The table compares them task by task.

Reach for an array when the count is known and fixed: the rainfall for each of the 12 months, the 9 squares of a tic-tac-toe board, the grids in the next lesson. Reach for an ArrayList when values arrive or leave while the program runs: a shopping basket, a waiting list, the results of a search. For a set of values that should never change, List.of gives you a list that cannot be changed by accident.

An array of numbers also takes less memory, because each number sits directly in its slot instead of inside its own Integer object. That matters for millions of numbers, and not for a class list.

1import java.util.ArrayList;
2 
3public class Main {
4    public static void main(String[] args) {
5        int[] readings = {7, 12, 3, 18, 20, 5, 9, 14};
6        ArrayList<Integer> evens = new ArrayList<>();
7 
8        // TODO: add every even reading to evens
9 
10        System.out.println(evens);
11        System.out.println(evens.size() + " even readings");
12    }
13}

Further reading#

• ArrayList in the Java SE 25 API documentation
• Unmodifiable lists, the rules for List.of, in the List documentation
• Extending Collection with List, on dev.java
• Iterating over the elements of a collection, on dev.java