Skip to content
Tutorials Center
My learning

Topics

Lesson 80 of 201 ยท Collections

ArrayList

Master Java ArrayList - add, get, set and remove, searching, safe removal while iterating, removeIf, subList views, sorting, capacity growth and performance.

ArrayList is the collection you'll reach for more than any other. It's a list that grows as you add to it, keeps elements in the order you put them, allows duplicates and gives you any element by its index in constant time. When a Java developer says "a list", they almost always mean an ArrayList.

Under the hood it's just an array with some bookkeeping: when the array fills up, ArrayList allocates a bigger one and copies everything across. Knowing that one fact explains which operations are fast, which are slow and how to use the class well. This lesson covers the full everyday API, the traps (removing while looping, remove(int) vs remove(Object), subList views) and the performance model.

Creating an ArrayList

Java
List<String> names = new ArrayList<>();                 // empty
List<String> copy = new ArrayList<>(otherCollection);   // a modifiable copy
List<Integer> big = new ArrayList<>(10_000);            // empty, room for 10,000
List<String> start = new ArrayList<>(List.of("a", "b")); // modifiable list with values

Declare the variable as List (see program to interfaces), and use the diamond <> so the compiler infers the element type. Elements must be objects, so a list of numbers is a List<Integer> and relies on autoboxing.

new ArrayList<>(List.of(...)) is the standard way to get a list that starts with values and can still change. List.of(...) alone is immutable.

Adding, reading, changing, removing

Java The everyday ArrayList operations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The key methods:

Method Returns Notes
add(e) / add(i, e) true / nothing add(i, e) shifts later elements right
addAll(c) / addAll(i, c) true if changed adds every element of another collection
get(i) element throws IndexOutOfBoundsException if i < 0 or i >= size()
set(i, e) old element replaces; doesn't change the size
remove(i) removed element shifts later elements left
remove(o) true if found removes the first element equals to o
getFirst() / getLast() element Java 21; throw NoSuchElementException if empty
size(), isEmpty(), clear()

Valid indexes run from 0 to size() - 1, except add(i, e), which also accepts i == size() (appending).

Searching

contains, indexOf and lastIndexOf walk the list and compare with equals:

Java Searching and the remove(int) trap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

contains finds the second, separate Book object because records implement equals by comparing fields. For your own classes, contains only works by value if you override equals (The Object Class). indexOf returns -1 when nothing matches.

The last lines repeat a pitfall from Wrapper Classes: with a List<Integer>, remove(2) removes index 2. Use remove(Integer.valueOf(2)) to remove a value.

Searching is a linear scan, so it gets slower as the list grows. If you check membership often in a big collection, use a HashSet (HashSet); if the list is sorted, Collections.binarySearch is much faster.

Looping and changing while you loop

All the usual loops work:

Java
for (int i = 0; i < list.size(); i++) { ... list.get(i) ... }   // when you need the index
for (String item : list) { ... }                                  // the default
list.forEach(item -> IO.println(item));                           // with a lambda

The trap is removing elements inside a for-each loop. The list's iterator notices that the list changed behind its back and throws ConcurrentModificationException. The correct tools are removeIf, an explicit Iterator, or looping backward by index:

Java Removing while iterating, wrong and right

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The broken loop doesn't even fail reliably. If the element you remove happens to be the second-to-last one, the loop simply ends early without any exception, silently skipping the last element. That's what makes the bug nasty. A forward index loop that removes elements has a different bug: after removing index i, the next element slides into position i and gets skipped.

removeIf is also the fastest option: it removes all matching elements in one pass, whereas repeated remove(i) calls shift the tail each time. replaceAll is its sibling for changing every element. Iterators and ListIterator explains how the "fail-fast" check works.

Sorting and sub-lists

list.sort(comparator) sorts in place; pass null or Comparator.naturalOrder() for natural order. subList(from, to) returns a view of a range (from inclusive, to exclusive) that reads and writes through to the original list:

Java sort and subList views

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

list.subList(a, b).clear() is the standard way to remove a range of elements. But a sub-list is tied to its parent: once you add or remove elements in the parent directly, the old view becomes invalid and any use throws ConcurrentModificationException. If you want to keep a slice around, copy it into a new list. More on comparators in Sorting with Comparable and Comparator.

Converting to and from arrays

Java
String[] array = names.toArray(String[]::new);    // List -> array of the right type
List<String> list = new ArrayList<>(Arrays.asList(array));   // array -> modifiable list
List<String> fixedView = Arrays.asList(array);    // fixed-size view backed by the array

Arrays.asList returns a fixed-size view (no add or remove), and it doesn't work for primitive arrays the way you'd expect: Arrays.asList(new int[] {1, 2}) is a List<int[]> with one element. For int[], use Arrays.stream(numbers).boxed().toList().

How ArrayList grows

An ArrayList has a size (how many elements it holds) and a capacity (the length of its internal array). When add finds the array full, it creates a new array about 1.5 times larger and copies the elements. One add occasionally costs a full copy, but averaged over many adds it's constant time ("amortized O(1)"): because the array grows in proportion to its size, the expensive copies become rarer and rarer as the list grows.

TEXT
capacity  10: [a b c d e f g h i j]      add k -> full!
capacity  15: [a b c d e f g h i j k . . . .]   copy 10, then add
capacity  22: ...                         the next copy happens at 15 elements

A new ArrayList<>() starts with an empty array and allocates room for 10 elements on the first add. If you know roughly how many elements are coming, pass that number to the constructor (new ArrayList<>(50_000)) or call ensureCapacity(n) to skip the intermediate copies. trimToSize() shrinks the array to the current size, which only matters for big, long-lived lists. Removing elements never shrinks the capacity on its own.

Performance

Because it's an array, an ArrayList is excellent at some things and poor at others:

Operation Cost Why
get(i), set(i, e) O(1) direct array access
add(e) at the end O(1) amortized occasional resize
add(i, e), remove(i) near the front O(n) shifts every later element
remove at the end, removeLast() O(1) nothing to shift
contains, indexOf, remove(o) O(n) linear search
removeIf, replaceAll, sort O(n), O(n), O(n log n) single pass / TimSort

The cost of shifting is easy to see:

Java Adding at the front vs at the end

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Inserting at the front copies the whole array on every call, so the total work grows with the square of n. Exact numbers vary between runs, but the gap is large and grows quickly with n. Despite that, ArrayList is still the right default: shifting uses a fast block memory copy, and arrays are friendly to CPU caches. If you truly need to add and remove at the front, use an ArrayDeque (Queues, Deques and PriorityQueue), and see the next lesson for why LinkedList is rarely the answer.

Other things to know

  • equals compares contents in order. Two lists are equal if they have the same elements in the same order, regardless of class: an ArrayList can equal a LinkedList or a List.of(...).
  • Not thread-safe. Sharing an ArrayList between threads that modify it corrupts it. Use the tools in Concurrent Collections.
  • null elements are allowed, but they make contains checks and sorting awkward. Avoid them when you can.
  • Return a copy or an unmodifiable view from a getter (List.copyOf(items)) so callers can't change your object's internal list (Encapsulation).

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does this print? List<String> l = new ArrayList<>(List.of("a", "b", "c")); l.add(1, "x"); System.out.println(l);

    add(1, "x") inserts at index 1 and shifts b and c to the right. It doesn't replace anything; that's set.
  2. 2. What does set(0, "z") return on the list [a, b]?

    set replaces the element at the index and returns the old value, which is handy for swaps and undo logic.
  3. 3. What is the safest way to remove all empty strings from a List<String> named items?

    removeIf removes every match in one pass. for-each + remove throws ConcurrentModificationException, a forward index loop skips elements, and remove("") removes only the first match.
  4. 4. Why is adding at index 0 of a large ArrayList slow?

    ArrayList is backed by an array, so inserting at the front copies all later elements one slot over, which is O(n) per insert.
  5. 5. List<Integer> view = list.subList(0, 2); view.clear(); What happens to list?

    subList returns a view backed by the original list, so clearing the view removes that range from the original.

Summary

  • ArrayList is a resizable array: ordered, indexed, duplicates allowed, the default List.
  • Core API: add, add(i, e), get, set (returns the old value), remove(i), remove(o), size, contains, indexOf, getFirst/getLast.
  • With List<Integer>, remove(2) removes an index; use remove(Integer.valueOf(2)) for a value.
  • Never remove inside a for-each loop; use removeIf, Iterator.remove or a backward index loop.
  • subList is a live view: great for clear() on a range, invalid after the parent changes structurally; copy it to keep it.
  • Capacity grows by about 1.5x with a copy; pre-size big lists. get/set and appends are fast; inserts, removals near the front and searches are O(n).

Next: LinkedList, a list made of linked nodes, and an honest look at when it beats ArrayList.