An ArrayList in Java is an array that grows. It stores its elements in a contiguous array behind the scenes and it keeps that array's length in step with your adds and removes. That is why you get the array speed for the indexed access and the array simplicity for the API, without having to manage the array yourself.
The previous lesson in this module covered "What Does the Collections Framework Give You?", and the next lesson in this module is about "Why Is HashMap the Default Choice for Key-Value Data?".
What does the array backing actually buy you?
Reading an element by index is a direct array read, so it stays at the constant time no matter how large the list is. Adding to the end is also at the constant time most of the time. The list keeps some spare room at the end and it shifts everything into it only when the spare room runs out. That pattern is the reason that appending to an ArrayList is described as the amortised constant time. There is occasional expensive work that is spread across many cheap ones.
Everything else costs more than you might expect, and the reason is always the same. The elements live next to each other in one array. Inserting in the middle or deleting from the middle means shifting the tail to close the gap, and that touches every element after that point.
| Operation | Typical cost | Why |
|---|---|---|
| get by index | constant | direct read from the backing array |
| add at the end | constant, amortised | spare capacity, occasional growth copy |
| find by value | linear | each element is compared in turn |
| remove by value | linear | search, then shift the tail left |
| insert or remove in the middle | linear | the tail has to move |
How do you control the backing array?
You rarely need to, but the two methods exist and knowing them avoids a surprise later. The method ensureCapacity grows the backing array up front so that a burst of adds does not repeatedly copy it, and the method trimToSize shrinks it back down to the number of elements that you actually hold.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ArrayListCapacityDemo {
public static void main(String[] args) {
ArrayList<String> items = new ArrayList<>(List.of("a", "b", "c"));
System.out.println("initial contents: " + items);
items.ensureCapacity(100);
items.add("d");
System.out.println("after adding one more: " + items);
System.out.println("size is " + items.size() + " but capacity was reserved up front");
items.trimToSize();
System.out.println("trimToSize keeps every element: " + items);
List<String> part = items.subList(0, 2);
System.out.println("subList view: " + part);
String[] array = items.toArray(new String[0]);
System.out.println("as an array: " + Arrays.toString(array));
List<String> copy = new ArrayList<>(items);
copy.set(0, "changed");
System.out.println("the copy is independent: " + copy + " vs " + items);
}
}The output is this.
initial contents: [a, b, c]
after adding one more: [a, b, c, d]
size is 4 but capacity was reserved up front
trimToSize keeps every element: [a, b, c, d]
subList view: [a, b]
as an array: [a, b, c, d]
the copy is independent: [changed, b, c, d] vs [a, b, c, d]The copy constructor at the end is the important one for the correctness. The call new ArrayList<>(items) takes a snapshot of the elements, so changing the copy leaves the original untouched. Assigning the list itself to a second variable would not do that, because both of the variables would point at the same list.
Which remove method did you call?
The ArrayList has two methods called remove and they do completely different things. The one that takes an int removes the element at that position. The one that takes an Object removes the first element that is equal to that value. With a list of numbers this is a genuine trap, because an integer literal silently picks the index version.
import java.util.ArrayList;
import java.util.List;
public class ArrayListBasicsDemo {
public static void main(String[] args) {
List<String> items = new ArrayList<>();
items.add("alpha");
items.add("beta");
items.add("gamma");
items.add("beta");
System.out.println("size: " + items.size());
System.out.println("indexOf beta: " + items.indexOf("beta"));
System.out.println("get(1): " + items.get(1));
System.out.println("contains gamma: " + items.contains("gamma"));
boolean removed = items.remove("beta");
System.out.println("removed the first beta: " + removed + " -> " + items);
List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30, 40));
numbers.remove(1);
System.out.println("remove(int index) drops position 1: " + numbers);
List<Integer> more = new ArrayList<>(List.of(10, 20, 30, 40));
more.remove(Integer.valueOf(20));
System.out.println("remove(Object) drops the value 20: " + more);
}
}The output is this.
size: 4
indexOf beta: 1
get(1): beta
contains gamma: true
removed the first beta: true -> [alpha, gamma, beta]
remove(int index) drops position 1: [10, 30, 40]
remove(Object) drops the value 20: [10, 30, 40]Look closely at the last two lines. The call numbers.remove(1) removed the element at the position one, which was the value 20 by coincidence. The call more.remove(Integer.valueOf(20)) removed the value 20 wherever it sat. The results look the same here because the value happened to be in that position. Change the order of the list and the two calls diverge.
Why does removing inside a for-each loop blow up?
The enhanced for loop works through an iterator, and the iterator notices that the list was structurally modified behind its back. That check exists because modifying a list while you are walking it leaves the iterator pointing at the wrong element, and the result is silent nonsense rather than a clean error.
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class ArrayListIterationDemo {
public static void main(String[] args) {
List<String> items = new ArrayList<>(List.of("one", "two", "three"));
try {
for (String item : items) {
if (item.equals("one")) {
items.remove(item);
}
}
} catch (RuntimeException e) {
System.out.println("removing inside for-each failed: " + e.getClass().getSimpleName());
}
System.out.println("the list is left half updated: " + items);
List<String> safe = new ArrayList<>(List.of("one", "two", "three"));
Iterator<String> iterator = safe.iterator();
while (iterator.hasNext()) {
if (iterator.next().equals("two")) {
iterator.remove();
}
}
System.out.println("iterator.remove left: " + safe);
}
}The output is this.
removing inside for-each failed: ConcurrentModificationException
the list is left half updated: [two, three]
iterator.remove left: [one, three]There are two things that are worth noticing. The exception arrives as a ConcurrentModificationException, which tells you that the modification was detected but it says nothing about what you did wrong. The fix is to remove through the iterator, as in the second half of the program. And the list is left in a half-updated state, because the removal happened before the check fired. That is why removing during the iteration is more than an inconvenience. It can leave your data in a state that you did not plan for.
When is an ArrayList the wrong choice?
There are three situations that call for something else. If your program inserts or removes at the front of a large list over and over, then every one of those operations shifts the whole list, and a linked structure that can unlink a node without moving anything serves you better. If you are queueing work, then use ArrayDeque, which is designed for adding at one end and removing from the other. If you need to look the elements up by value often, then use a set or a map instead, because an ArrayList has to walk its elements to answer a membership question.
There is also a memory consideration. An ArrayList of the primitives stores the boxed objects, one object per element plus the pointer to it, so a list of a million numbers costs far more memory than a plain int[]. For a fixed set of values that never changes size, the primitive array is still the better tool.
ArrayList in brief
- It is a resizable array, with the constant-time indexed reads and the amortised constant-time appends.
- Finding and removing by value is linear, because the elements sit side by side in one array.
- The call
remove(int)takes a position, and the callremove(Object)takes a value. - Never modify the list while you are walking it with a for-each loop. Use
Iterator.remove()or copy the list first. - Copy with
new ArrayList<>(other)when you need an independent snapshot.
Try it yourself: build a list of ten names, and then remove every name that starts with the letter "a" using an iterator, and print what is left. Next, write the same removal using removeIf with a lambda and confirm that the result matches. Finally, create a list of the integers 1 to 5, call remove(1), and print the list. Then repeat with remove(Integer.valueOf(1)) and explain the difference in one sentence.