Какова временная сложность вставки элемента в ArrayList и LinkedList в Java?

«Какова временная сложность вставки элемента в ArrayList и LinkedList в Java?» — вопрос из категории Алгоритмы и структуры данных, который задают на 10% собеседований Java Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

Временная сложность (Big O) вставки зависит от позиции и внутренней реализации коллекций.

ArrayList (реализация на динамическом массиве)

  • Вставка в конец (add(E element)): O(1) амортизированная.
    • Большинство операций выполняются за константное время.
    • При заполнении внутреннего массива происходит его увеличение (обычно в 1.5 раза) и копирование всех элементов — операция O(n), но она случается редко, что дает амортизированную O(1).
  • Вставка в начало или середину (add(int index, E element)): O(n).
    • Требует сдвига всех элементов, находящихся правее позиции вставки.
List<String> arrayList = new ArrayList<>();
arrayList.add("End");       // O(1) амортизированное
arrayList.add(0, "Start");  // O(n) — сдвиг всех элементов вправо

LinkedList (реализация на двусвязном списке)

  • Вставка в начало (addFirst(E) / add(0, E)): O(1).
    • Требуется только создать узел и обновить ссылки head.
  • Вставка в конец (addLast(E) / add(E)): O(1).
    • Если хранится ссылка на tail (как в Java).
  • Вставка в середину по индексу (add(int index, E element)): O(n).
    • Время уходит на поиск нужной позиции (требуется обход с начала или конца). Сама вставка после поиска — O(1).
List<String> linkedList = new LinkedList<>();
linkedList.addFirst("Start"); // O(1)
linkedList.add("End");        // O(1)
linkedList.add(1, "Middle");  // O(n) — поиск позиции с индексом 1

Сводная таблица

Операция ArrayList LinkedList
Вставка в конец O(1) амортизированная O(1)
Вставка в начало O(n) O(1)
Вставка в середину (по индексу) O(n) (сдвиг) O(n) (поиск)

Практический вывод: Выбирайте ArrayList для частых операций доступа по индексу и вставки в конец. LinkedList может быть эффективнее при частых вставках/удалениях в начале списка или при работе через итератор.