BrewlearnArrayList in Java
Resizable array: fast get, amortized O(1) add, slow middle insert.
A row of numbered lockers
An **ArrayList stores elements in an internal array**. Element i lives at a computed position, so get(i) and set(i, x) jump straight there: O(1), no walking.
List<String> list = new ArrayList<>();
list.add("A"); // [A]
list.add("C"); // [A, C]
list.get(1); // "C", instantlyInserting shifts everyone
add(i, x) doesn't overwrite. It shifts every later element one slot right to make room, so inserting or removing in the middle costs O(n).
list.add(1, "B"); // [A, B, C]
// "C" moved from index 1 to index 2
list.remove(0); // [B, C], all shift leftYour turn
What does this print?
List<String> list = new ArrayList<>();
list.add("x");
list.add("z");
list.add(0, "w");
System.out.println(list + " " + list.size());[x, w, z] 3[w, x, z] 3[w, z] 2
Show the answer
add(0, "w") inserts at the front and pushes x and z right. Nothing is replaced, so the size grows to 3.
When the lockers run out
When the array is full, ArrayList allocates one about 1.5× bigger and copies everything. That copy is O(n), but it gets rarer as the list grows. Averaged over all adds, appending stays constant: amortized O(1).
// capacity 10 → 15 → 22 → 33 → ...
for (int i = 0; i < 1_000; i++) {
list.add("item"); // rare copies
}Capacity is not size
This list has room for 100 elements. What happens?
List<Integer> list = new ArrayList<>(100);
System.out.println(list.get(0));Prints nullPrints 0Throws IndexOutOfBoundsException
Show the answer
**new ArrayList<>(100) sets the capacity (internal storage), not the size. The list is still empty**, so index 0 is out of bounds. Valid indexes go from 0 to size() - 1.
Building a list in reverse
for (String s : input) {
list.add(0, s); // shifts all
}Every front insert shifts the whole list. A million items means about a trillion moves.
for (String s : input) {
deque.addFirst(s); // ArrayDeque
}ArrayDeque.addFirst is O(1). Or append to an ArrayList and call Collections.reverse once.
Where it bites
ArrayList is the default list in almost every Java codebase. Two habits pay off: pass a capacity when you know the size (new ArrayList<>(n)) to skip the resize copies, and never insert at index 0 in a loop. That pattern has turned plenty of import jobs from seconds into hours.
Key takeaways
- get(i) and set(i, x): O(1)
- add(x) at the end: amortized O(1) — occasional resize copies
- add(i, x) / remove(i) in the middle: O(n) because elements shift
- Capacity (internal array length) is not the same as size()
💡 An ArrayList is a row of numbered lockers: you can walk straight to locker 57, but squeezing a new locker in the middle means moving every locker after it.
In modern JDKs, new ArrayList<>() doesn't allocate its first 10-slot array until you add something. All empty ArrayLists share one empty array, which saves memory when you create many lists that stay empty.
Practice questions
What does this print?
List<String> list = new ArrayList<>();
list.add("A");
list.add("C");
list.add(1, "B");
System.out.println(list + " " + list.size());- [A, C, B] 3
- [A, B, C] 3
- [B, A, C] 3
- [A, B, C] 2
Check your answer
[A, B, C] 3. add(1, "B") inserts at index 1 and shifts "C" one place right. Nothing is overwritten, so the size becomes 3.
Why is ArrayList.add(x) at the end described as *amortized* O(1)?
- Every add copies the whole array, but the JIT hides the cost
- It's O(1) only if you passed an initial capacity
- Occasionally the full array must be copied into a bigger one, but that's rare enough that the average cost per add stays constant
- Adding is always exactly O(1); 'amortized' is just a label
Check your answer
Occasionally the full array must be copied into a bigger one, but that's rare enough that the average cost per add stays constant. Because the array grows by a factor (~1.5×), resizes become rarer as the list grows. Spread across all adds, the copying averages out to a constant cost.