Какая временная сложность метода append для LinkedList и ArrayList

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

Знаете ли вы, что добавление в конец у обоих постоянное, и понимаете ли разницу между амортизированной и гарантированной оценкой.

Как отвечать

Добавление в конец у обоих списков за постоянное время, но по разным причинам и с разной оговоркой.

ArrayList это массив. Пока в нём есть свободная ёмкость, добавление это запись по индексу, то есть O(1). Когда место кончилось, создаётся новый массив примерно в полтора раза больше и старый копируется, это O(n). Такое случается редко, и стоимость размазывается: оценка амортизированная O(1). Отдельная вставка иногда дорогая, но серия из n вставок стоит O(n).

LinkedList это двусвязный список, у которого хранится ссылка на хвост. Добавление в конец это создание узла и перевязка двух ссылок, гарантированная O(1) без всяких оговорок.

Разница появляется в других операциях, и о ней стоит сказать сразу:

• вставка по индексу в середину: у ArrayList O(n) на сдвиг хвоста, у LinkedList тоже O(n), но на поиск позиции. Ускорения нет ни у кого;
• доступ по индексу: O(1) против O(n);
• вставка в начало: O(n) против O(1).

Практический вывод важнее асимптотики. ArrayList почти всегда быстрее на реальных данных: элементы лежат в памяти подряд и хорошо попадают в кэш процессора, а копирование делается быстрой системной операцией. LinkedList тратит на каждый элемент отдельный объект с двумя ссылками и прыгает по памяти.

В Kotlin это стоит помнить, потому что mutableListOf() и arrayListOf() создают именно ArrayList, и это правильный выбор по умолчанию. Для очереди с двух концов берут ArrayDeque, а не LinkedList.

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

Говорят, что у ArrayList добавление O(n) из-за расширения, забывая про амортизацию.

Считают, что LinkedList быстрее вставляет по индексу.

Не могут объяснить, что такое амортизированная сложность.

Выбирают LinkedList для очереди вместо ArrayDeque.