ArrayList
A growable array. The default choice for a list, and usually the right one.
List<String> names = new ArrayList<>();
names.add("Ada");
names.add("Grace");
names.get(0); // "Ada"
names.size(); // 2
Declare the variable as List and construct an ArrayList. Coding to the interface means swapping the implementation later touches one line.
What it is
An array underneath, plus a size. When it fills, a larger array is allocated and the contents copied. That copy is why add is amortised constant time, usually instant, occasionally a copy, averaging out cheap.
If you know roughly how many elements you need, say so and skip the copies:
new ArrayList<>(10_000);
Costs
| Operation | Cost |
|---|---|
get(i), set(i, x) |
constant |
add(x) at the end |
amortised constant |
add(i, x), remove(i) |
linear, everything after it shifts |
contains(x), indexOf(x) |
linear. It compares each element |
The two to watch are inserting or removing in the middle of a large list, and calling contains in a loop. The second is the more common performance bug: a contains inside a loop over another collection is quadratic, and a HashSet makes it linear.
Versus a plain array
An array has fixed length and can hold primitives. ArrayList grows and works with the collections library, but holds objects only. An ArrayList<Integer> boxes every value, costing memory and time. For a large quantity of numbers where that matters, int[] is the honest answer.
Versus LinkedList
LinkedList offers constant-time insertion at a known position, but you rarely have one. Finding it is linear, and its poor memory locality means it loses in practice more often than the theory suggests. Use ArrayList unless you have measured a reason not to. For a queue or a deque, ArrayDeque beats both.
Removing while iterating
Removing inside a for-each throws ConcurrentModificationException. Use:
names.removeIf(String::isEmpty);
Fixed-size and immutable lists
List.of("a", "b") // immutable
Arrays.asList(array) // fixed size, writes through to the array
new ArrayList<>(List.of("a")) // mutable copy
Arrays.asList catches people out: add throws, but set works and modifies the underlying array.