Класс Java ArrayList | W3Docs Learn Java

ArrayList<E> — это главная реализация интерфейса List. Внутри хранится обычный Java-массив (Object[]) со счётчиком длины и логикой роста. Это определяет характеристики производительности, которые нужны большинству программ: O(1) произвольный доступ, амортизированное O(1) добавление в конец и редкие паузы при расширении массива. Когда говорят «используй список», не уточняя какой, почти всегда имеют в виду ArrayList. В этой главе объясняется, почему, в чём компромиссы и какие методы уникальны для этого класса.

Что внутри

ArrayList хранит три части состояния:

Object[] elementData — внутренний массив. Длиннее size на некоторый запас.
int size — количество занятых слотов.
int modCount — счётчик, нарушающий работу итераторов при изменении во время итерации.

В документации точно описана сложность: size, isEmpty, get, set, iterator, listIterator и add (в конец) работают за константное время. Вставка и удаление в любом другом месте выполняются за линейное время, потому что хвост массива нужно сдвигать. Вернёмся к этому ниже.

Создание

List<String> a = new ArrayList<>();             // default capacity (10)
List<String> b = new ArrayList<>(1_000_000);    // pre-size — avoids re-grows
List<String> c = new ArrayList<>(otherList);    // copy of any Collection
List<String> d = new ArrayList<>(List.of("a", "b", "c"));   // from a small literal

Если вы примерно знаете, сколько элементов будет добавлено, передайте ёмкость в конструктор. Ёмкость по умолчанию равна 10, и каждый раз, когда массив заполняется, он увеличивается примерно на 50% — что означает множество выделений памяти и копирований, если добавлять миллионы элементов начиная с начального значения. Однострочное исправление:

List<Row> rows = new ArrayList<>(expectedSize);

Для «из этого фиксированного набора» предпочтительнее фабрика List.of(...) (рассматривается далее в этой главе) — она компактнее и неизменяема.

Добавление и удаление — стоимость зависит от позиции

Каждый List.add(E), add(int, E), remove(int) и remove(Object) в худшем случае выполняется за O(n), если затрагивает середину массива. Причина механическая: массив — это смежная память, поэтому вставка в начало означает, что каждый существующий элемент нужно сдвинуть на один слот вправо. Амортизированная стоимость добавления в конец составляет O(1) (без сдвига), но для любой другой позиции она линейна по числу элементов после точки вставки.

На практике это означает:

Построение списка через list.add(x) → быстро, независимо от размера. Добавление в конец — то, для чего предназначен ArrayList.
Вызов list.add(0, x) в цикле → квадратичная сложность. Не делайте этого.
Повторный вызов list.remove(0) для опустошения → квадратичная сложность. Используйте Deque или итерируйте в обратном порядке.

Если вы постоянно вставляете или удаляете элементы с начала, ArrayDeque — подходящий инструмент.

Ёмкость и размер

Это два разных числа:

size() — публичный счётчик элементов на уровне контракта.
Ёмкость — длина внутреннего массива — является внутренней и больше size.

Когда запас заканчивается, ArrayList выделяет новый массив примерно в 1.5× длиннее предыдущего и копирует данные. Это и есть «рост», о котором предупреждает документация. Два рычага управления:

ensureCapacity(int) — увеличить внутренний массив как минимум до этой длины до ожидаемой серии вызовов add.
trimToSize() — уменьшить внутренний массив до ровно size. Полезно, когда вы знаете, что список больше не будет расти (например, перед долгим кэшированием).

Ни то ни другое вы не будете использовать часто, но полезно знать, что они есть, при оптимизации горячего пути.

`ArrayList` не является потокобезопасным

Два потока, изменяющие один и тот же ArrayList, в конечном счёте его повредят. Синхронизации нет, атомарных операций нет, ничего. Если нужен параллельный доступ, варианты следующие:

Collections.synchronizedList(new ArrayList<>()) — оборачивает каждый модифицирующий метод блокировкой. Итераторы по-прежнему небезопасны — во время итерации нужно синхронизироваться внешне. Подходит для случаев с низкой конкуренцией.
CopyOnWriteArrayList — каждая мутация выделяет новую копию внутреннего массива. Итерация не блокируется и видит замороженный снимок. Отлично подходит для «много читателей, редкий писатель» (обработчики событий, конфигурационные кэши). Плохой выбор для интенсивных записей.
Vector — также синхронизирован, но дизайн 1995 года с теми же слабостями, что и synchronizedList. Не используйте в новом коде.

Многопоточность — отдельная глубокая тема; правило на сейчас такое: ArrayList, разделяемый между потоками, требует обёртки или другого класса.

Итерация и `ConcurrentModificationException`

Добавление или удаление из ArrayList во время итерации по нему через цикл for-each почти всегда бросает ConcurrentModificationException:

List<Integer> xs = new ArrayList<>(List.of(1, 2, 3, 4));
for (int x : xs) {
  if (x % 2 == 0) xs.remove(Integer.valueOf(x));   // throws
}

Проверка fail-fast сравнивает снимок modCount итератора с текущим modCount списка. Два способа безопасно мутировать:

xs.removeIf(x -> x % 2 == 0);              // 1. predicate form — cleanest

Iterator<Integer> it = xs.iterator();
while (it.hasNext())                        // 2. explicit Iterator.remove()
  if (it.next() % 2 == 0) it.remove();

removeIf — современный вариант по умолчанию. К явному итератору прибегайте только когда условие зависит от состояния, которое вы не хотите вычислять дважды.

Полезные методы, которых нет в `List`

ArrayList добавляет несколько методов, отсутствующих в интерфейсе List:

void trimToSize() — уменьшить до нужного размера.
void ensureCapacity(int) — предварительно увеличить.
Object clone() — поверхностная копия. Эквивалентна new ArrayList<>(this) и почти никогда не используется.

Вот и всё. Почти всё, что вы будете вызывать на ArrayList, взято из интерфейса List.

Рабочий пример: ArrayList в действии

Программа ниже создаёт ArrayList, задействует его операции с индексами, опустошает его и завершается сравнением времени с предварительным заданием ёмкости и без него, чтобы вы могли увидеть стоимость забытого предварительного размера.

java— editable, runs on the server

import java.util.*;

public class ArrayListInMotion {
  public static void main(String[] args) {
    // --- Building ---
    List<String> fruits = new ArrayList<>();
    fruits.add("apple");
    fruits.add("banana");
    fruits.add("cherry");
    fruits.add(1, "avocado");      // insert at index 1 — shifts tail right
    System.out.println("after build:    " + fruits);
    System.out.println("size():         " + fruits.size());

// --- Index access ---
    System.out.println("get(2):         " + fruits.get(2));
    fruits.set(0, "apricot");
    System.out.println("after set:      " + fruits);

// --- Search ---
    System.out.println("indexOf(cherry):    " + fruits.indexOf("cherry"));
    System.out.println("contains(grape):    " + fruits.contains("grape"));

// --- The two remove overloads ---
    fruits.remove(0);                       // by index
    fruits.remove("banana");                // by value
    System.out.println("after both removes: " + fruits);

// --- Safe mutation during iteration ---
    List<Integer> nums = new ArrayList<>(List.of(1, 2, 3, 4, 5, 6));
    nums.removeIf(n -> n % 2 == 0);
    System.out.println("odd only:       " + nums);

// --- Slicing with subList (a live view) ---
    List<Integer> ints = new ArrayList<>(List.of(10, 20, 30, 40, 50));
    List<Integer> middle = ints.subList(1, 4);   // view of [20, 30, 40]
    middle.replaceAll(x -> x * 10);
    System.out.println("after view edit: " + ints);

// --- Pre-sizing vs default-sizing for a million appends ---
    int N = 1_000_000;

long t1 = System.nanoTime();
    List<Integer> defaultList = new ArrayList<>();
    for (int i = 0; i < N; i++) defaultList.add(i);
    long defaultMs = (System.nanoTime() - t1) / 1_000_000;

long t2 = System.nanoTime();
    List<Integer> sizedList = new ArrayList<>(N);
    for (int i = 0; i < N; i++) sizedList.add(i);
    long sizedMs = (System.nanoTime() - t2) / 1_000_000;

System.out.println("\nappend " + N + " elements:");
    System.out.println("  default capacity: ~" + defaultMs + " ms");
    System.out.println("  pre-sized:        ~" + sizedMs  + " ms");
    System.out.println("  (the default constructor re-grows the backing array ~30 times getting there)");
  }
}

Порядок операций, который нужно считать из вывода:

fruits.add(1, "avocado") сдвинул каждый последующий элемент на один слот вправо. Для четырёх элементов это незаметно; для миллиона это стало бы доминирующим фактором времени выполнения.
removeIf и subList — два механизма, делающих большую часть реального кода с ArrayList чистой — удаление по предикату и операции с живым окном.
Блок измерения времени носит иллюстративный характер, а не является полноценным бенчмарком — при единственном запуске с прогревом JIT числа могут выйти даже в обратном порядке. Главный вывод структурный: добавление с ёмкостью по умолчанию перерасширяет внутренний массив около 30 раз к миллионному элементу, а предварительное задание ёмкости устраняет все эти копирования. Для стабильного горячего пути предварительно заданная версия выигрывает; измеряйте с помощью нормального инструмента, если это важно.

Что дальше

ArrayList — правильный ответ почти всегда. Интересен тот случай, когда он не является таковым — интенсивные вставки и удаления в начале или середине длинного списка. Это ниша LinkedList: тот же интерфейс List, совершенно другое хранилище. Одна задача, два решения — и мы измерим, когда каждое из них выигрывает.

Практика

Вы собираетесь прочитать CSV-файл из 5 миллионов строк в `List<Row>`, добавляя по одной строке за раз. Какая настройка `ArrayList` даёт заметный выигрыш в производительности по сравнению с конструктором по умолчанию?

`new ArrayList<>(5_000_000)` — предварительное задание ёмкости пропускает ~33 цикла роста и копирования, которые вызвал бы конструктор по умолчанию`new ArrayList<>()`, а затем вызывать `ensureCapacity(5_000_000)` раз за каждые 100 тысяч строк для обрезки массива`new LinkedList<>()` — связанные узлы никогда не требуют изменения размера, поэтому добавление всегда постоянно по времени без пауз роста`Collections.synchronizedList(new ArrayList<>())` — блокировка предотвращает параллельные записи и избегает конкуренции при изменении размера