Что такое двунаправленный список?

Двунаправленный список (Doubly Linked List)

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

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

template <typename T>
struct Node {
    T data;
    Node* next;      // Указатель на следующий узел
    Node* prev;      // Указатель на предыдущий узел
};

// Внешне:
// prev <- Node -> next

Схема двунаправленного списка

null <- [Data1] <-> [Data2] <-> [Data3] -> null
        (prev)      (next/prev)   (next)

Реализация базовых операций

template <typename T>
class DoublyLinkedList {
private:
    struct Node {
        T data;
        Node* next;
        Node* prev;
        
        Node(const T& value) 
            : data(value), next(nullptr), prev(nullptr) {}
    };
    
    Node* head;
    Node* tail;
    size_t size;

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}

    // Добавление в конец
    void push_back(const T& value) {
        Node* new_node = new Node(value);
        
        if (tail == nullptr) {
            head = tail = new_node;
        } else {
            tail->next = new_node;
            new_node->prev = tail;
            tail = new_node;
        }
        size++;
    }

    // Добавление в начало
    void push_front(const T& value) {
        Node* new_node = new Node(value);
        
        if (head == nullptr) {
            head = tail = new_node;
        } else {
            new_node->next = head;
            head->prev = new_node;
            head = new_node;
        }
        size++;
    }

    // Удаление с конца
    void pop_back() {
        if (tail == nullptr) return;
        
        Node* temp = tail;
        if (tail->prev) {
            tail = tail->prev;
            tail->next = nullptr;
        } else {
            head = tail = nullptr;
        }
        delete temp;
        size--;
    }

    // Удаление с начала
    void pop_front() {
        if (head == nullptr) return;
        
        Node* temp = head;
        if (head->next) {
            head = head->next;
            head->prev = nullptr;
        } else {
            head = tail = nullptr;
        }
        delete temp;
        size--;
    }
};

Преимущества двунаправленного списка

1. Двусторонняя навигация — можно идти вперёд и назад
2. Вставка/удаление за O(1) — если уже знаешь позицию (нужны оба указателя)
3. Реверс без переворота — можно просто менять направление движения

// Итерация вперёд
for (Node* curr = head; curr; curr = curr->next) {
    process(curr->data);
}

// Итерация назад
for (Node* curr = tail; curr; curr = curr->prev) {
    process(curr->data);
}

Недостатки двунаправленного списка

1. Больше памяти — два указателя на узел вместо одного
2. Сложнее поддерживать — нужно синхронизировать оба указателя
3. Медленный поиск — O(n) для поиска элемента
4. Нет случайного доступа — нельзя взять i-й элемент за O(1)

// Плохо: O(n)
T get_at(int index) {
    Node* curr = (index < size / 2) ? head : tail;
    int i = (index < size / 2) ? 0 : size - 1;
    
    while (i != index) {
        curr = (index < size / 2) ? curr->next : curr->prev;
        i += (index < size / 2) ? 1 : -1;
    }
    return curr->data;
}

Сравнение: однонаправленный vs двунаправленный

Где используется

1. std::list в C++ STL — двунаправленный список
2. Deque операции — нужна быстрая работа с обоих концов
3. LRU Cache — нужна навигация в обоих направлениях
4. Undo/Redo — нужно ходить по истории туда-сюда

#include <list>

int main() {
    std::list<int> list = {1, 2, 3, 4, 5};
    
    // Итерация вперёд
    for (auto it = list.begin(); it != list.end(); ++it) {
        std::cout << *it << " ";  // 1 2 3 4 5
    }
    
    // Итерация назад
    for (auto it = list.rbegin(); it != list.rend(); ++it) {
        std::cout << *it << " ";  // 5 4 3 2 1
    }
}

Удаление элемента по итератору

auto it = list.begin();
++it;  // На второй элемент
list.erase(it);  // O(1) удаление благодаря двум указателям

Вывод: Двунаправленный список предоставляет баланс между гибкостью навигации и простотой реализации, идеален для сценариев, где нужна работа с обоих концов структуры и частые вставки/удаления в известных позициях.