В чем разница linked list и array list по времени доступа и вставки

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

Понимаете ли вы, как устроены обе коллекции внутри, а не только таблицу из учебника. Почти всегда следом спрашивают, когда вы в последний раз брали LinkedList в Android-проекте и чем бы его заменили.

Как отвечать

Начните с устройства: ArrayList держит ссылки на элементы в массиве, LinkedList это двусвязный список из отдельных узлов. Отсюда вся асимптотика:

• доступ по индексу: у ArrayList O(1), это адресная арифметика. У LinkedList O(n): get(i) идёт от ближайшего конца, то есть до n/2 шагов;
• вставка в конец: у ArrayList амортизированное O(1). Когда массив заполнен, создаётся новый, примерно в полтора раза больше, и данные копируются;
• вставка в середину: у ArrayList O(n) из-за сдвига хвоста, но это один System.arraycopy, он очень быстрый. У LinkedList O(1) только если узел уже найден, например через ListIterator.add. Вызов add(index, e) сначала ищет узел за O(n);
• память: каждый узел LinkedList это отдельный объект с заголовком и двумя ссылками. Накладные расходы в разы выше, а сборщик мусора получает больше мелких объектов.

Ключевой вывод: на реальных размерах ArrayList выигрывает почти всегда за счёт локальности данных в кэше процессора. В Kotlin mutableListOf() и так возвращает ArrayList, а для очереди или стека есть ArrayDeque. LinkedList оправдан редко: частые вставки и удаления в середине через итератор, когда позиция уже известна.

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

Говорят «вставка в LinkedList всегда O(1)» и забывают, что сначала нужно дойти до места вставки.

Обходят LinkedList циклом for (i in 0 until list.size) list[i]. Каждый get проходит список заново, и обход становится квадратичным.

Не упоминают амортизацию: O(1) для вставки в конец ArrayList верно в среднем, отдельная вставка с расширением массива стоит O(n). Если размер известен заранее, помогает начальная ёмкость в конструкторе.