Как удалить элемент из односвязного списка, имея ссылку на предыдущий элемент

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

Базовое владение ссылками и граничными случаями, без опоры на библиотеки. Следом обычно спрашивают сложность, как удалить голову списка и как удалить узел, если дана ссылка только на него самого.

Как отвечать

Суть в одной операции: prev.next = prev.next.next. Удаляемый узел выпадает из цепочки, и сборщик мусора ART заберёт его, когда на него не останется других ссылок. На Kotlin, который обычно просят на лайвкодинге:

class Node(val value: Int, var next: Node? = null)

fun removeAfter(prev: Node) {
    val target = prev.next ?: return
    prev.next = target.next
    target.next = null
}

Что проговорить вслух:

• сложность: O(1) по времени и памяти, ведь предыдущий узел искать не нужно. Без ссылки на него поиск занял бы O(n);
• граничные случаи: prev оказался последним (удалять нечего); удаляется хвост (если список хранит tail, его переносят на prev); удаляется голова (у неё нет предыдущего, поэтому перед head ставят фиктивный узел dummy);
• обнуление target.next: для сборщика мусора не обязательно, но если на удалённый узел где-то осталась ссылка, он не будет держать живым весь хвост списка, и из него нельзя случайно продолжить обход;
• счётчик: если список хранит size, его уменьшают.

Смежная задача: удалить узел, имея ссылку только на него. Копируют значение следующего узла в текущий и удаляют следующий. Для последнего узла трюк не работает, и это стоит сказать самому, не дожидаясь вопроса.

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

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

Не проверяют prev.next на null и получают NullPointerException при попытке удалить элемент после хвоста.

Забывают про голову и хвост: первый элемент такой функцией не удалить, а поле tail после удаления последнего продолжает указывать на выброшенный узел.

Рассказывают про освобождение памяти, как в C. В JVM и ART отцепить ссылку и есть весь шаг. Обратная ошибка: думать, что узел исчезнет, пока на него ссылается, например, адаптер RecyclerView или кеш.