Сколько стоит получение элемента по индексу в LinkedList?

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.