Двусвязный список

Ссылки в обе стороны

В двусвязном списке узел хранит две связи: next ведёт вперёд, а prev — назад. Поэтому, имея ссылку на конкретный узел, можно сразу добраться до обоих его соседей.

class Node {
    int value;
    Node prev;
    Node next;

    Node(int value) {
        this.value = value;
    }
}

За удобство приходится платить дополнительной ссылкой в каждом узле и более аккуратным обновлением структуры: при вставке или удалении обычно нужно поддержать согласованность сразу двух направлений.

Удаление известного узла

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

if (node.prev != null) {
    node.prev.next = node.next;
}

if (node.next != null) {
    node.next.prev = node.prev;
}

Количество переназначений постоянно, поэтому само удаление известного узла выполняется за O(1). Однако границы списка всё равно требуют внимания: при удалении головы или хвоста нужно обновить внешние ссылки head или tail.

Когда двусвязность полезна

Двусвязная структура удобна, когда алгоритму нужно двигаться в обе стороны, быстро удалять уже найденные узлы или поддерживать доступ к обоим концам списка. Если движение назад не требуется, дополнительная ссылка prev может быть лишней.