Что хотят услышать интервьюеры:

В ArrayList вставка в середину выполняется через сдвиг всех элементов справа на одну позицию. После этого новый элемент записывается в освободившуюся ячейку. Поэтому операция стоит не O(1), а O(n) из-за копирования элементов.

Определение:

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

Пример использования:

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("C");

        list.add(1, "B"); // вставка в середину

        System.out.println(list); // [A, B, C]
    }
}

Пояснение кода:

Код не требуется, но пример работает так:

В списке есть элементы A и C.
Вызывается add(1, "B"), то есть вставка на позицию с индексом 1.
Элемент C сдвигается вправо.
В освободившуюся позицию помещается B.
Итоговый порядок: A, B, C.

Ключевые моменты:

Вставка в середину ArrayList требует сдвига элементов вправо.
Временная сложность операции — O(n).
Если не хватает емкости массива, происходит расширение внутреннего массива.
Доступ по индексу остается быстрым — O(1).
Для частых вставок в середину ArrayList обычно менее выгоден, чем структуры со связанными узлами.

Как осуществляется добавление элемента в середину массива в структуре ArrayList?