O(n): произвольного доступа нет, до позиции нужно дойти по ссылкам (JDK начинает с ближнего конца).
sottofor (i...) list.get(i) по LinkedList — квадратичная сложностьА ещё На практике ArrayList почти всегда быстрее: память подряд и кэш процессора
Так подсказку видит пользователь sotto на живом собеседовании — за пару секунд, пока вы думаете вслух.
LinkedList — двусвязный список: каждый элемент хранится в отдельном узле со ссылками на предыдущий и следующий. Адрес пятидесятого элемента вычислить нельзя — нужно пройти по цепочке. Реализация в JDK идёт с того конца, который ближе к индексу, но сложность всё равно O(n).
Отсюда практическая ловушка: обход LinkedList по индексам в цикле for (int i = 0; i < list.size(); i++) list.get(i) превращает линейный проход в квадратичный. Перебирать нужно через for-each или итератор.
Миф «вставка в LinkedList дешёвая» верен только частично: сама вставка узла — O(1), но сначала до места вставки нужно дойти за O(n). Дешевы только добавление и удаление у концов и удаление через итератор во время обхода.
На реальном железе ArrayList обычно выигрывает и там, где по теории должен проигрывать: элементы лежат в памяти подряд и хорошо попадают в кэш процессора, а у узлов LinkedList ещё и большой расход памяти на ссылки. Для очереди и стека лучше ArrayDeque.
Один верный вариант. Подумайте, потом откройте ответ.
Двусвязные узлы, реальная стоимость операций, cache locality и почему ArrayList/ArrayDeque почти всегда лучше.
sotto слышит вопрос интервьюера и показывает короткий ответ и план, как в блоке «Коротко». Оставьте контакт — пришлём доступ и промокод.