Что такое двусвязный список (Doubly Linked List)?

Двусвязный список — это линейная структура данных, состоящая из узлов (nodes), где каждый узел содержит:

1. Данные (payload).
2. Указатель на следующий узел (next).
3. Указатель на предыдущий узел (prev).

Наличие двух ссылок позволяет эффективно обходить список в обоих направлениях (вперёд и назад) и упрощает некоторые операции, такие как удаление произвольного узла, если известен только он сам, а не его предшественник.

Реализация узла и базовых операций на C++:

#include <iostream>

template <typename T>
class DoublyLinkedList {
private:
    struct Node {
        T data;
        Node* prev;
        Node* next;
        Node(const T& value, Node* p = nullptr, Node* n = nullptr)
            : data(value), prev(p), next(n) {}
    };
    Node* head_;
    Node* tail_;
    size_t size_;

public:
    DoublyLinkedList() : head_(nullptr), tail_(nullptr), size_(0) {}

    ~DoublyLinkedList() { clear(); }

    void push_back(const T& value) {
        Node* newNode = new Node(value, tail_, nullptr);
        if (tail_) {
            tail_->next = newNode;
        } else { // Список был пуст
            head_ = newNode;
        }
        tail_ = newNode;
        ++size_;
    }

    void erase(Node* node) {
        if (!node) return;
        // Корректируем связи соседних узлов
        if (node->prev) node->prev->next = node->next;
        if (node->next) node->next->prev = node->prev;
        // Корректируем head и tail, если удаляемый узел был ими
        if (node == head_) head_ = node->next;
        if (node == tail_) tail_ = node->prev;
        delete node;
        --size_;
    }

    void clear() {
        while (head_) {
            Node* toDelete = head_;
            head_ = head_->next;
            delete toDelete;
        }
        tail_ = nullptr;
        size_ = 0;
    }

    void printForward() const {
        for (Node* curr = head_; curr; curr = curr->next) {
            std::cout << curr->data << " ";
        }
        std::cout << std::endl;
    }

    void printBackward() const {
        for (Node* curr = tail_; curr; curr = curr->prev) {
            std::cout << curr->data << " ";
        }
        std::cout << std::endl;
    }
};

int main() {
    DoublyLinkedList<int> list;
    list.push_back(10);
    list.push_back(20);
    list.push_back(30);
    std::cout << "Forward:  "; list.printForward();  // 10 20 30
    std::cout << "Backward: "; list.printBackward(); // 30 20 10
    return 0;
}

*Удаление в односвязном списке за O(1) возможно, если скопировать данные из следующего узла в удаляемый и удалить следующий узел, но это не всегда применимо.

Применение в C++: Стандартный контейнер std::list реализован как двусвязный список.