Чем односвязный список отличается от двусвязного?

В односвязном списке узел хранит только указатель на следующий элемент, а в двусвязном — ещё и на предыдущий: двусвязный позволяет движение в обе стороны и удаление узла за O(1), но стоит больше памяти и кода.

Односвязный

• Обход только вперёд; удаление узла требует указателя на предыдущий, иначе поиск за O(n).
• Минимум памяти: один указатель на узел. Используется в стеках, цепочках хеш-таблиц, lock-free структурах.

Двусвязный

• Удаление и вставка по указателю на сам узел за O(1) — критично для LRU-кеша и очередей.
• Два указателя на узел и вдвое больше переприсваиваний при каждой операции — выше шанс ошибиться.

Полезные приёмы

• Фиктивные guard-узлы (head и tail) убирают особые случаи пустого списка.
• Разворот односвязного списка за O(n) — классическая задача на три указателя.
• Середина за один проход: быстрый и медленный указатели.

Коротко для собеседования

Двусвязный список нужен, когда узел надо удалять или переставлять за O(1) по ссылке на него самого, — классический пример LRU-кеш. Платишь лишним указателем на узел и большим числом переприсваиваний, поэтому там, где хватает прохода вперёд, берут односвязный.