Что нужно сделать перед вставкой элемента в середину LinkedList

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

Понимаете ли вы, что у связного списка дёшева только перелинковка, а добраться до середины стоит O(n). Вопрос отсеивает тех, кто выучил «вставка в LinkedList за O(1)» и не задумывался, откуда берётся ссылка на нужный узел.

Как отвечать

Перед вставкой надо получить узел, после которого встанет новый: без него менять нечего. В java.util.LinkedList этим занимается внутренний node(index). Он проверяет границы (значение index == size допустимо, это вставка в конец) и идёт с того конца списка, который ближе к индексу, так что обход в худшем случае это половина списка.

Дальше сама вставка:

• список двусвязный, у узла есть prev и next, поэтому правятся четыре ссылки, а не две;
• вставка в начало и в конец это отдельные ветки с полями first и last;
• растут size и modCount, из-за второго ранее взятые итераторы становятся невалидными.

Когда узел уже найден, вставка занимает константное время. Поэтому при нескольких вставках подряд держат позицию итератором, а не ищут её заново по индексу:

ListIterator<String> it = list.listIterator(index);
it.add("a");   // позиция известна, поиска нет
it.add("b");

Уместно добавить, что в реальном коде ArrayList чаще быстрее: сдвиг хвоста через System.arraycopy обходится дешевле, чем прыжки по узлам мимо кэша процессора.

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

Говорят «вставка в LinkedList за O(1)» и на этом останавливаются. Константа относится к перелинковке, а add(index, e) включает поиск, то есть O(n). Честная формулировка: константа при наличии ссылки на узел или итератора.

Меняют список во время обхода в цикле for-each и ловят ConcurrentModificationException. Добавлять внутри обхода можно только через ListIterator.add, он сам обновляет modCount и позицию курсора.

Пишут свой односвязный узел и теряют половину случаев: пустой список, вставка перед головой, обновление хвоста и размера. Отдельно проверяют границы: index == size валиден, всё что больше это IndexOutOfBoundsException.