Как работает алгоритм расширения ArrayList

Что проверяют

Знаете ли вы реальную реализацию из JDK, а не общую идею динамического массива, и понимаете ли, откуда берётся амортизированная константа у add.

Как отвечать

• Внутри обычный Object[] elementData плюс поле size. size это число элементов, elementData.length это ёмкость, путать их нельзя.
• new ArrayList<>() массив не выделяет: поле указывает на общий пустой массив, и ёмкость 10 появляется только при первом add.
• При добавлении проверяется size == elementData.length, и если места нет, вызывается внутренний grow. Новая ёмкость считается как oldCapacity + (oldCapacity >> 1), то есть рост в полтора раза, а не вдвое. Если этого мало (скажем, при addAll большой коллекции), берётся требуемый минимум; сверху ёмкость ограничена значением около Integer.MAX_VALUE.
• Копирует Arrays.copyOf через нативный System.arraycopy, но по стоимости это всё равно O(n).
• Отсюда амортизированная O(1) на вставку в конец: геометрический рост даёт суммарно O(n) копирований на n вставок, при этом отдельная вставка в момент расширения стоит O(n).
• ensureCapacity(n) это публичный метод для резерва заранее: его зовут руками, когда размер известен, сам рост идёт не через него.
• Массив никогда не сжимается: remove сдвигает хвост влево и уменьшает size, ёмкость остаётся. Освобождает память только trimToSize().

List<String> list = new ArrayList<>(10_000); // без расширений
list.add("a");                               // амортизированно O(1)
list.add(0, "b");                            // O(n): сдвиг вправо

Где спотыкаются

Говорят про рост вдвое. Вдвое растёт Vector, а ArrayList увеличивается в 1.5 раза, и это любимая проверка.

Считают, что new ArrayList<>() сразу выделяет массив на 10 ссылок. Выделение ленивое, его запускает первый add.

Смешивают size() и ёмкость и делают вывод, будто после удаления половины элементов список отдал память.

Утверждают, что вставка в середину дешёвая. Она стоит O(n) на сдвиг, а у LinkedList дешёвая вставка требует сначала дойти до позиции, что тоже O(n).