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

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

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

Как отвечать

Сначала механика: чтобы вставить в середину, нужен узел перед позицией вставки, а его надо найти обходом, это O(n). java.util.LinkedList двусвязный, обход идёт с ближнего конца, поэтому в худшем случае проходится половина списка. Сама перелинковка потом константная: правятся prev и next у соседей и у нового узла, обновляются size и modCount, из-за последнего живые итераторы протухают. Если вставок несколько, позицию держат итератором:

val it = list.listIterator(index)
it.add(item)   // поиска нет, вставка за константу

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

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

Повторяют, что вставка в связный список за O(1), и забывают про поиск позиции. Константа честна только тогда, когда ссылка на узел уже есть. На типичных для экрана объёмах данных ArrayList выигрывает даже на вставке в середину: сдвиг массива это один быстрый System.arraycopy.

Меняют коллекцию во время обхода и получают ConcurrentModificationException. Внутри цикла добавлять можно только через итератор, а если список показан в RecyclerView, менять его на месте нельзя вовсе: адаптеру отдают новый список, а разницу считает DiffUtil.

Пишут свой односвязный узел и теряют краевые случаи: пустой список, вставка перед головой, обновление хвоста и размера. Ещё правят данные адаптера из фонового потока. Изменение списка и уведомление адаптера идут на главном потоке, иначе данные и UI разъезжаются.