Демо: двусвязный список

Структура узла

объявление

struct Node {
    int data;          // полезные данные
    Node *prev;        // ← указатель на предыдущий
    Node *next;        // → указатель на следующий
};

// Для доступа к списку храним ДВА указателя:
Node *Head = nullptr;   // первый узел
Node *Tail = nullptr;   // последний узел

Что это даёт по сравнению с односвязным:

Можно идти по списку в обоих направлениях.
Удаление узла не требует поиска предыдущего — он уже есть в поле prev.
Добавление перед узлом — тривиальная операция.
Указатель на Tail позволяет добавлять в конец за O(1), а не за O(n).

Цена: на каждый узел тратится дополнительный указатель (8 байт на 64-битной системе).

Список

Список пуст.

Операции

Значение

Ключ (для «после»/«перед»/«удалить»)

Журнал операций

Журнал пуст.

Ключевые операции

AddFirst — добавление в начало

void AddFirst(Node *&Head, Node *&Tail, Node *NewNode) {
    NewNode->next = Head;
    NewNode->prev = nullptr;

    if (Head) Head->prev = NewNode;  // бывшая голова смотрит назад
    Head = NewNode;

    if (!Tail) Tail = Head;          // если список был пуст
}

AddAfter — добавление после заданного узла

void AddAfter(Node *&Head, Node *&Tail, Node *p, Node *NewNode) {
    if (p->next == nullptr) {         // p — последний узел
        NewNode->next = nullptr;
        NewNode->prev = p;
        p->next = NewNode;
        Tail = NewNode;
    } else {
        // ПОРЯДОК ВАЖЕН: сначала настраиваем поля нового узла,
        // потом — соседей
        NewNode->next = p->next;
        NewNode->prev = p;
        p->next->prev = NewNode;
        p->next = NewNode;
    }
}

Delete — удаление узла (без поиска!)

void Delete(Node *&Head, Node *&Tail, Node *OldNode) {
    if (Head == OldNode) {
        Head = OldNode->next;
        if (Head) Head->prev = nullptr;
        else Tail = nullptr;           // удалили единственный элемент
    } else {
        OldNode->prev->next = OldNode->next;
        if (OldNode->next)
            OldNode->next->prev = OldNode->prev;
        else
            Tail = OldNode->prev;      // удалили последний
    }
    delete OldNode;
}

Порядок операций критичен. В AddAfter если сначала поменять p->next, мы потеряем адрес следующего узла и не сможем настроить его prev. Всегда сначала настраиваем новый узел, потом его соседей.

Главное преимущество двусвязного списка. Удаление узла — O(1), если у вас уже есть указатель на этот узел. В односвязном списке пришлось бы сначала пройти от головы, чтобы найти предыдущий узел — то есть O(n).

Задание

Добавьте три узла в конец списка (AddLast). Сравните с AddFirst — как меняется положение Head и Tail?
Удалите узел, стоящий в середине. Сколько указателей нужно обновить? А сколько было бы в односвязном?
Добавьте узел перед ключом (AddBefore). Поменяйте местами две строки — что произойдёт?
Реализуйте операцию «разворот списка» через обмен prev и next у каждого узла.
На базе двусвязного списка реализуйте структуру «Дек» — вставка и удаление с обоих концов за O(1).
Почему при удалении последнего узла нужно отдельно обрабатывать случай, когда он же и единственный?