Java ArrayList
›Short versionOpen if you only have a minute.
- ArrayList is a list on a growable array. get and set by index are constant time.
- add at the end is amortized constant time. A full array is copied into a larger one, about 1.5 times as long.
- add or remove at index i shifts the tail, so it is linear in the number of elements after i.
- Pass an initial capacity when the final size is known, so growth copies do not dominate.
- Iterators are fail-fast. Structural edits belong to the iterator, or to removeIf.
- This is the default List. Reach for another implementation only for a cost ArrayList charges too much.
An is the list you want when the program reads by position more often than it splices in the middle. The element at index 40 is one array lookup, whether the list holds 50 names or 50,000.
The spare room at the end of the array is . Filling it, then growing, is why append is described as rather than constant time on every single call.
Where the linear work hides
A is the cost people forget. Removing index 0 copies every remaining element down one slot. Doing that inside a loop over a long list copies about n, then n − 1, then n − 2 elements. The total is quadratic. Build the result in a fresh list, or remove from the end, when you need to drop many front elements.
contains and indexOf are also linear. They walk until equals matches. An ArrayList is the wrong tool for “have I seen this key?” once that question dominates. A HashSet answers it in average constant time.
The iterator is . It is a bug detector for structural changes made by the list itself during a walk. It is not a lock, and it is not a promise about other threads.
Reads, appends, and one careful delete
List<String> cars = new ArrayList<>(8);
cars.add("Volvo");
cars.add("BMW");
cars.set(0, "Tesla"); // O(1)
cars.add(1, "Audi"); // shifts the tail
cars.remove(cars.size() - 1); // no shift
Iterator<String> it = cars.iterator();
while (it.hasNext()) {
if (it.next().equals("Audi")) {
it.remove(); // updates the iterator's expected count
}
}A million appends start from an ArrayList with the default capacity. Roughly how many times is the backing array copied, and how do you make that number one?
The array starts small and grows by about half each time, so a million appends cause a handful of copies, on the order of log base 1.5 of a million. new ArrayList<>(1_000_000) or ensureCapacity(1_000_000) allocates once, and the appends only fill slots.