Удаление узла и вставка нового элемента в двусвязный список

Условие

Необходимо реализовать функции удаления и вставки узлов в структуру двусвязного списка.

Требования:

• Удалять узел, исходя из переданного значения.
• Вставлять новый узел сразу после указанного узла.

Особое внимание следует уделить граничным ситуациям:

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

class Node {
    private Integer value;
    private Node next;
    private Node prev;
}

class LinkedList {
    private Node head;
    private Node tail;

    public void remove(Integer value) {
        // TODO
    }

    public void add(Integer prev, Integer next, Integer value) {
        // TODO
    }
}

Ответ

При удалении узла соедините его prev и next, отдельно обновив head/tail на границах. При вставке между соседями нужно установить четыре связи и при необходимости новые границы списка.

Для удаления найденного x: если x.prev != null, задайте x.prev.next = x.next, иначе head = x.next; если x.next != null, задайте x.next.prev = x.prev, иначе tail = x.prev. Затем обнулите ссылки x. Для вставки n между p и q: n.prev=p, n.next=q; p.next=n либо head=n; q.prev=n либо tail=n. Сигнатура add(Integer prev, Integer next, Integer value) передаёт значения, не узлы: при дубликатах выбор неоднозначен. Лучше передавать узел либо явно определить поиск первого совпадения и проверить соседство. Доступ к private-полям обеспечьте вложенным Node или методами.