Ответ
Временная сложность (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 может быть эффективнее при частых вставках/удалениях в начале списка или при работе через итератор.