ArrayList: size vs capacity, and how it beats an array

A set list that keeps changing#

Picture the sheet of paper taped to the stage floor at a small gig: the band’s set list. Before the show it gets rewritten again and again. A song is added at the end, a new one is squeezed in at the top, a slow one is cut, two are swapped. No band in history has played the set list it wrote at the first rehearsal.

The arrays guide ended with a pattern for exactly this: the oversized array with a count. You write the adding, finding and removing yourself:

String[] songs = new String[6];           // the sheet: 6 lines
int count = 0;                            // how many lines are in use
songs[count] = "Gravel Road"; count++;    // add at the first empty line

You chose the size and keep count up to date by hand. A seventh song would not fit at all.

An ArrayList is that same pair, the array and the count, packed into one object with the methods already written. That is the one new part. Underneath it is still an ordinary oversized array, hidden from you. This guide builds one program, SetList, around that sheet, and shows the real output at every step.

import java.util.ArrayList;

public class SetList {
    public static void main(String[] args) {
        ArrayList<String> songs = new ArrayList<>();   // the array and its count, in one object
        songs.add("Gravel Road");
        songs.add("Static Bloom");
        songs.add("Northbound");
        System.out.println(songs + " size " + songs.size());
    }
}

[Gravel Road, Static Bloom, Northbound] size 3

Every symbol, named:

• import java.util.ArrayList;: ArrayList lives in the java.util package.
• ArrayList<String>: the type in the angle brackets, < and >, says what the list holds. It is called a type argument, part of generics, which has its own guide next.
• new ArrayList<>(): makes an empty list. The empty angle brackets, called the diamond, tell Java to copy the type from the left side.
• songs.add(x) puts x at the end. songs.size() returns how many items are in the list: it is the count variable, kept for you.

Like an array, a list counts from 0, so its last item is at index size() - 1.

What an ArrayList does that an array does not#

Side by side:

Arrays still win on two counts: they hold primitive values such as int directly, and they are a little faster and lighter. When the count is fixed, an array is fine. When items come and go, use an ArrayList.

Python’s list grows on its own; Java gives you both a fixed array and a growing list, and expects you to pick.

Adding, reading, finding and removing#

Every array operation has an ArrayList method, and the comments say what each call does. Two need a closer look: add(i, x) inserts and slides every later item one place right, and set(i, x) replaces without sliding anything.

import java.util.ArrayList;

public class SetList {
    public static void main(String[] args) {
        ArrayList<String> songs = new ArrayList<>();
        songs.add("Gravel Road");                      // add at the end
        songs.add("Static Bloom");
        songs.add("Northbound");
        songs.add("Last Ferry");
        songs.add(1, "Paper Moonlight");               // insert at index 1; later songs slide right
        System.out.println(songs);

        System.out.println("Opener: " + songs.get(0)); // read one item
        String old = songs.set(3, "Slow Burn");        // replace one item; returns the old one
        System.out.println("Swapped out " + old + ": " + songs);

        System.out.println(songs.contains("Slow Burn"));    // true or false
        System.out.println(songs.indexOf("Static Bloom"));  // first index that matches
        System.out.println(songs.indexOf("Northbound"));    // -1 means not found

        boolean cut = songs.remove("Static Bloom");    // by value: returns true or false
        String dropped = songs.remove(0);              // by index: returns the item removed
        System.out.println(cut + ", dropped " + dropped + ": " + songs);
    }
}

[Gravel Road, Paper Moonlight, Static Bloom, Northbound, Last Ferry]
Opener: Gravel Road
Swapped out Northbound: [Gravel Road, Paper Moonlight, Static Bloom, Slow Burn, Last Ferry]
true
2
-1
true, dropped Gravel Road: [Paper Moonlight, Slow Burn, Last Ferry]

Either kind of remove closes the gap, and the size drops by 1. remove("Static Bloom") returned true (it returns false if nothing matches). remove(0) returned the song it took out.

contains, indexOf and remove(x) all compare items with equals, not ==. That is why the Object guide’s advice about overriding equals(Object) matters for your own classes.

Numbers, loops and methods#

The sound engineer keeps one number per song, in set order: how many minutes it runs. The obvious first try is ArrayList<int>. Here is what the compiler says, shown on purpose so you recognize it:

import java.util.ArrayList;

public class SetList {
    public static void main(String[] args) {
        ArrayList<int> minutes = new ArrayList<>();
    }
}

SetList.java:5: error: unexpected type
        ArrayList<int> minutes = new ArrayList<>();
                  ^
  required: reference
  found:    int
1 error

“Required: reference, found: int” means a type argument must be a reference type (a class), not a primitive type such as int or double. That is why the wrapper classes exist: Integer wraps one int in an object, and Double, Boolean and Character do the same for theirs. So the list is an ArrayList<Integer>.

You still write plain numbers. Java turns an int into an Integer on the way in, which is called autoboxing. It turns an Integer back into an int on the way out, which is called unboxing. Most of the time you will not notice. The remove trap in the next section is where you will.

Both loops from the arrays guide work on a list, with size() for length and get(i) for [i]. A method that takes a list gets a copy of the reference, the arrow to the one list, just as with an array. The program now fills the list in one line. List.of (from java.util.List) makes a list that cannot be changed (no add, set or remove). The ArrayList constructor copies it into one you can change.

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

public class SetList {
    public static int total(ArrayList<Integer> values) {
        int sum = 0;                       // the accumulator starts at 0
        for (int v : values) {             // each Integer is unboxed to an int
            sum += v;
        }
        return sum;
    }

    public static void main(String[] args) {
        ArrayList<Integer> minutes = new ArrayList<>(List.of(4, 3, 6, 5, 3));
        int sum = total(minutes);
        System.out.println("Set length: " + sum + " min");
        System.out.println("Average song: " + sum / minutes.size() + " min");

        int longest = 0;                   // index of the longest song so far
        for (int i = 1; i < minutes.size(); i++) {
            if (minutes.get(i) > minutes.get(longest)) {
                longest = i;
            }
        }
        System.out.println("Longest: " + minutes.get(longest) + " min, at index " + longest);
    }
}

Set length: 21 min
Average song: 4 min
Longest: 6 min, at index 2

The total is right. total uses the accumulator pattern: sum starts at 0 before the loop, grows by one value per pass, and is read after the loop ends. The longest-song search is the arrays-guide pattern with get(i) in place of [i]. It assumes index 0 is the longest and lets the loop prove otherwise from index 1.

Now the average. Does 4 make sense? You predicted 4.2. Because 4 sits between the shortest song (3) and the longest (6), it looks possible, and that is how this mistake slips through. Do the same check when a tool or an AI gives you an answer: decide roughly what it should be, then compare.

With that cast, the middle line prints Average song: 4.2 min. Nothing in total is about music, so it adds up any list of Integers, which is why its parameter is called values.

public static ArrayList<Integer> longSongs(ArrayList<Integer> values, int min) {
    ArrayList<Integer> result = new ArrayList<>();
    for (int v : values) {
        if (v >= min) {
            result.add(v);             // no counting pass: the list grows
        }
    }
    return result;
}

[6, 5]
[4, 3, 6, 5, 3]

The remove(int) versus remove(Object) trap#

The set is running long, so the engineer wants to cut the 3-minute song. The obvious call is minutes.remove(3).

remove is overloaded: there are two methods with the same name and different parameter types. remove(int index) removes by position. remove(Object o) removes by value. Java picks the one that matches what you pass most exactly, and 3 is an int.

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

public class SetList {
    public static void main(String[] args) {
        ArrayList<Integer> minutes = new ArrayList<>(List.of(4, 3, 6, 5, 3));
        minutes.remove(3);                       // meant: cut the 3-minute song
        System.out.println(minutes);

        minutes = new ArrayList<>(List.of(4, 3, 6, 5, 3));
        minutes.remove(Integer.valueOf(3));      // the value 3, as an object
        System.out.println(minutes);
    }
}

[4, 3, 6, 3]
[4, 6, 5, 3]

The first line shows the trap: the 5 vanished, and nothing warned you. To remove by value, hand remove an object instead of an int. Integer.valueOf(3) makes an Integer holding 3, so Java picks remove(Object). It removed only the first 3, the one at index 1, and left the second.

Here autoboxing does not step in: Java first looks for a method that fits without boxing, and remove(int) does.

Removing while you loop#

The slot just got shorter, so the new rule is: cut every song longer than 4 minutes. The list is now 4, 6, 5, 3.

Both methods below change the caller’s list through their copy of the arrow. Here values.remove(i) passes an int on purpose, because this time we mean the index.

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

public class SetList {
    public static void cutForward(ArrayList<Integer> values, int max) {
        for (int i = 0; i < values.size(); i++) {
            if (values.get(i) > max) {
                values.remove(i);                // the next song slides into index i
            }
        }
    }

    public static void cutBackward(ArrayList<Integer> values, int max) {
        for (int i = values.size() - 1; i >= 0; i--) {
            if (values.get(i) > max) {
                values.remove(i);                // only checked songs slide
            }
        }
    }

    public static void main(String[] args) {
        ArrayList<Integer> a = new ArrayList<>(List.of(4, 6, 5, 3));
        cutForward(a, 4);
        System.out.println("forward:  " + a);

        ArrayList<Integer> b = new ArrayList<>(List.of(4, 6, 5, 3));
        cutBackward(b, 4);
        System.out.println("backward: " + b);

        ArrayList<Integer> c = new ArrayList<>(List.of(4, 6, 5, 3));
        c.removeIf(m -> m > 4);                  // remove every m where m > 4
        System.out.println("removeIf: " + c);
    }
}

forward:  [4, 5, 3]
backward: [4, 3]
removeIf: [4, 3]

The forward loop removed only one of the two long songs. After a removal, the next item moves into index i, and i++ skips straight past it.

Shrink it to the smallest case. Take just the two long songs, [6, 5]. Forward: at i = 0 the 6 is removed, leaving [5]. Then i becomes 1, the condition 1 < 1 is false, and the loop ends with the 5 still there. Backward: i starts at 1 and the 5 is removed; then i becomes 0 and the 6 is removed. The list is empty, which is right.

Looping backward fixes it because the only items that slide are ones the loop has already checked. removeIf does the whole job in one call. You give it a lambda, a tiny unnamed method: m -> m > 4 reads as “given m, answer whether m > 4”. Every item that answers true is removed.

What about removing inside a for-each loop? Here is its strange output, on purpose:

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

public class SetList {
    public static void main(String[] args) {
        ArrayList<Integer> d = new ArrayList<>(List.of(4, 6, 5, 3));
        for (int m : d) {
            if (m > 4) {
                d.remove(Integer.valueOf(m));
            }
        }
        System.out.println("for-each: " + d);
    }
}

Exception in thread "main" java.util.ConcurrentModificationException
	at java.base/java.util.ArrayList$Itr.checkForComodification(ArrayList.java:1095)
	at java.base/java.util.ArrayList$Itr.next(ArrayList.java:1049)
	at SetList.main(SetList.java:7)

A for-each loop walks the list with a hidden helper object called an iterator, and the iterator noticed the change and threw a ConcurrentModificationException. The check is not guaranteed: removing the second-to-last item, for example, just ends the loop early and skips the last item. Never call remove on a list inside a for-each loop over that same list.

Size versus capacity#

An ArrayList is an oversized array plus a count. Two numbers describe it:

• Size: how many items are in the list, returned by size(). Only indexes below it are usable.
• Capacity: the length of the hidden array: how many items fit before it must grow. It is never less than the size.

When an add needs more room, the ArrayList makes a bigger hidden array and copies every item across. The documentation promises some things and leaves others open:

• new ArrayList<>() starts with a capacity of ten. new ArrayList<>(20) starts with 20, which saves some copying when you know roughly how many items are coming.
• How much it grows is not specified; the only promise is that adding is cheap on average. (OpenJDK today grows it by about half, but that is not a rule.) There is no method that reports the capacity. ensureCapacity(n) grows it ahead of time and trimToSize() shrinks it to fit, and neither changes the size.

import java.util.ArrayList;

public class SetList {
    public static void main(String[] args) {
        ArrayList<String> songs = new ArrayList<>(20);   // room for 20, holds 0
        System.out.println("size " + songs.size());
        songs.add("Gravel Road");
        System.out.println("size " + songs.size() + ", opener " + songs.get(0));
        songs.set(1, "Static Bloom");
    }
}

size 0
size 1, opener Gravel Road
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 1 out of bounds for length 1
	at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:100)
	at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:106)
	at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:302)
	at java.base/java.util.Objects.checkIndex(Objects.java:385)
	at java.base/java.util.ArrayList.set(ArrayList.java:470)
	at SetList.main(SetList.java:9)

Read the message closely: “Index 1 out of bounds for length 1”. The length it checks is the size, 1, not the capacity of 20. You must add an item before you can get or set its index.

Vector, the older cousin#

Vector is an older class built on the same idea, with almost the same methods. It can report its capacity, so it is the place to watch the hidden array grow.

Its growth rule is documented. new Vector<>() starts with capacity 10 and a capacity increment of 0, which means “double when full”. new Vector<>(4, 2) starts at 4 and grows by 2 each time.

import java.util.Vector;

public class SetList {
    public static void main(String[] args) {
        Vector<String> songs = new Vector<>();
        System.out.println("size " + songs.size() + ", capacity " + songs.capacity());
        for (int i = 1; i <= 10; i++) {
            songs.add("Song " + i);
        }
        System.out.println("size " + songs.size() + ", capacity " + songs.capacity());
        songs.add("Song 11");
        System.out.println("size " + songs.size() + ", capacity " + songs.capacity());

        Vector<String> tight = new Vector<>(4, 2);       // start at 4, grow by 2
        for (int i = 1; i <= 5; i++) {
            tight.add("Song " + i);
        }
        System.out.println("size " + tight.size() + ", capacity " + tight.capacity());
    }
}

size 0, capacity 10
size 10, capacity 10
size 11, capacity 20
size 5, capacity 6

The eleventh song doubled the capacity to 20. The fifth song grew tight from 4 to 6.

A thread is one line of work inside a running program, and some programs run several at once. The differences exams ask about:

It is the same trade as StringBuilder versus StringBuffer in the Strings guide. The synchronized one is safe to share between threads, and it pays for that in speed. For single-threaded programs like every one in this guide, use ArrayList.

What was new in this guide#

1. ArrayList<String>: an oversized array and its count in one object.
2. add, add(i, x), get, set and size().
3. contains, indexOf and the two kinds of remove, all using equals.
4. ArrayList<Integer>, autoboxing and unboxing.
5. Lists in loops, as parameters and as return values.
6. The remove(int) versus remove(Object) trap.
7. Removing in a loop: backward, removeIf, never for-each.
8. Size versus capacity.
9. Vector: synchronized, doubling, older.

Where these go wrong#

• ArrayList<int>. Type arguments must be classes. Write ArrayList<Integer>.
• Using length, length() or square brackets on a list. A list uses size() and get(i).
• list.remove(3) on a list of Integers when you meant the value 3. That removes index 3. Use remove(Integer.valueOf(3)).
• Removing while looping forward. The next item slides into the gap and is skipped. Loop backward, or use removeIf.
• Removing inside a for-each loop. It usually throws ConcurrentModificationException, and when it does not, it skips items.
• Thinking new ArrayList<>(20) gives 20 items. It gives capacity 20 and size 0. get(0) fails until you add.
• Comparing two elements with ==. Use equals. == compares the arrows, which can surprise you for Integer values outside -128 to 127.

On the exam: if a question says “write a method”, write only the method: its header, its body and its return. If it says “write a program”, include the class, the import and main. Read the question, read it again, answer it, then read it once more to check you did every part.

Practice#

Answer each one on paper before you look at the solutions. Every answer that involves running code was checked by compiling and running it.

1. Give three advantages of an ArrayList over an array, and one advantage of an array.
2. What prints?

   ArrayList<String> q = new ArrayList<>();
   q.add("A");
   q.add("B");
   q.add(0, "C");
   q.add("D");
   q.remove(1);
   q.set(1, "E");
   System.out.println(q + " " + q.size());

3. An ArrayList<Integer> holds [1, 5, 9]. What is the list after list.remove(1)? What would list.remove(Integer.valueOf(1)) have left instead?
4. Write a method that removes every String shorter than min characters from an ArrayList<String>.
5. Explain the difference between size and capacity. After new ArrayList<>(50) and three calls to add, what are they?
6. Name three differences between Vector and ArrayList.

Solutions#

1. An ArrayList grows and shrinks automatically; it inserts and removes in the middle with one call, shifting for you; and it has built-in searching (contains, indexOf) and printing. An array can hold primitives directly and is slightly faster and lighter.
2. Step by step: [A], [A, B], [C, A, B], [C, A, B, D], remove index 1 gives [C, B, D], then set index 1 gives [C, E, D]:

   import java.util.ArrayList;
   
   public class QTrace {
       public static void main(String[] args) {
           ArrayList<String> q = new ArrayList<>();
           q.add("A");
           q.add("B");
           q.add(0, "C");
           q.add("D");
           q.remove(1);
           q.set(1, "E");
           System.out.println(q + " " + q.size());
       }
   }

   [C, E, D] 3

3. remove(1) passes an int, so it removes the item at index 1, the 5, leaving [1, 9]. remove(Integer.valueOf(1)) passes an object, so it removes the first item equal to 1, leaving [5, 9].
4. Loop backwards so removals never cause a skip:

   import java.util.ArrayList;
   
   public class QLong {
       public static void removeShort(ArrayList<String> words, int min) {
           for (int i = words.size() - 1; i >= 0; i--) {
               if (words.get(i).length() < min) {
                   words.remove(i);
               }
           }
       }
   
       public static void main(String[] args) {
           ArrayList<String> w = new ArrayList<>();
           w.add("a");
           w.add("an");
           w.add("apple");
           w.add("ox");
           w.add("banana");
           removeShort(w, 3);
           System.out.println(w);
       }
   }

   [apple, banana]

5. Size is how many items the list holds; capacity is how many the hidden array can hold before it must grow. Here size is 3 and capacity is 50.
6. Vector is synchronized (safe for several threads) and so slower; it doubles its capacity when it grows unless you set a capacity increment, while the documentation does not say how much an ArrayList grows; Vector has a capacity() method; and Vector is the older class (Java 1.0) kept for legacy code, while ArrayList is the modern default.

Test-readiness checklist#

These are the items from the course’s Exam 2 topic list that this guide covers. Tick each one only when you can do it without looking.

• ☐  I can list the advantages of an ArrayList over an array.
• ☐  I can explain the relationship between size and capacity.
• ☐  I can apply the array operations (declare, iterate, find, add, remove, pass and return) to an ArrayList.
• ☐  I can avoid the remove(int) trap and the forward-loop removal trap.
• ☐  I can explain what a Vector is and the differences between Vectors and ArrayLists.

Frequently asked questions#

Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.