Как хранится элемент в двусвязном списке?

Двусвязный список — структура элемента

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

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

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

template<typename T>
struct Node {
    T data;           // Данные
    Node* next;       // Указатель на следующий узел
    Node* prev;       // Указатель на предыдущий узел
    
    // Конструктор
    Node(const T& value) : data(value), next(nullptr), prev(nullptr) {}
};

Каждый узел занимает в памяти: sizeof(T) + sizeof(Node*) + sizeof(Node*) байт.

Пример с целыми числами

// Узел с данными int
struct IntNode {
    int data;      // 4 байта (на большинстве систем)
    IntNode* next; // 8 байт (на x64)
    IntNode* prev; // 8 байт (на x64)
};

// sizeof(IntNode) = 4 + 8 + 8 = 20 байт (с выравниванием может быть 24)

Визуальное представление

Двусвязный список: [A] <-> [B] <-> [C] <-> [D]

Узел B:
┌─────────────────────┐
│ Node                │
├─────────────────────┤
│ data: B             │
│ prev: ─────> [A]    │
│ next: ─────> [C]    │
└─────────────────────┘

Узел A (первый):
┌─────────────────────┐
│ Node                │
├─────────────────────┤
│ data: A             │
│ prev: nullptr       │  <- нет предыдущего
│ next: ─────> [B]    │
└─────────────────────┘

Узел D (последний):
┌─────────────────────┐
│ Node                │
├─────────────────────┤
│ data: D             │
│ prev: ─────> [C]    │
│ next: nullptr       │  <- нет следующего
└─────────────────────┘

Реализация двусвязного списка

#include <iostream>
using namespace std;

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;
    int size;
    
public:
    DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
    
    // Добавление в конец
    void push_back(const T& value) {
        Node* new_node = new Node(value);
        
        if (head == nullptr) {
            head = tail = new_node;
        } else {
            new_node->prev = tail;
            tail->next = new_node;
            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;
        tail = tail->prev;
        
        if (tail != nullptr) {
            tail->next = nullptr;
        } else {
            head = nullptr;
        }
        
        delete temp;
        size--;
    }
    
    // Удаление из начала
    void pop_front() {
        if (head == nullptr) return;
        
        Node* temp = head;
        head = head->next;
        
        if (head != nullptr) {
            head->prev = nullptr;
        } else {
            tail = nullptr;
        }
        
        delete temp;
        size--;
    }
    
    // Обход в прямом направлении
    void display_forward() {
        Node* current = head;
        cout << "Forward: ";
        while (current != nullptr) {
            cout << current->data << " <-> ";
            current = current->next;
        }
        cout << "nullptr\n";
    }
    
    // Обход в обратном направлении
    void display_backward() {
        Node* current = tail;
        cout << "Backward: ";
        while (current != nullptr) {
            cout << current->data << " <-> ";
            current = current->prev;
        }
        cout << "nullptr\n";
    }
    
    ~DoublyLinkedList() {
        while (head != nullptr) {
            pop_front();
        }
    }
};

int main() {
    DoublyLinkedList<int> list;
    
    list.push_back(10);
    list.push_back(20);
    list.push_back(30);
    list.push_front(5);
    
    list.display_forward();   // Forward: 5 <-> 10 <-> 20 <-> 30 <-> nullptr
    list.display_backward();  // Backward: 30 <-> 20 <-> 10 <-> 5 <-> nullptr
    
    return 0;
}

Сравнение со связным списком

Однусвязный список (singly linked):

struct Node {
    int data;
    Node* next;  // только forward
};

• Меньше памяти на указатели
• Быстрее добавление в начало
• Обход только в одну сторону

Двусвязный список (doubly linked):

struct Node {
    int data;
    Node* next;  // forward
    Node* prev;  // backward
};

• Больше памяти (два указателя вместо одного)
• Обход в обе стороны
• Удаление легче (знаем предыдущий узел)
• Балансировка и операции на конце эффективнее

Операции и их сложность

Память на элемент

Для int на x64:

Node<int> size = 4 (data) + 8 (next) + 8 (prev) = 20 байт

Для большого объекта:

struct Person {
    string name;      // переменный размер
    int age;          // 4 байта
    string email;     // переменный размер
};

Node<Person> size = sizeof(Person) + 16 байт (два указателя)

Кольцевой двусвязный список

Особая разновидность, где последний элемент ссылается на первый:

// Кольцевой список: [A] <-> [B] <-> [C] <-> [A] (циклически)

// head->prev указывает на tail
// tail->next указывает на head

Это позволяет:

• Обходить список циклически
• Эффективно реализовать структуры типа deque
• Использовать в алгоритме Josephus

Практическое применение

1. std::list в C++ — использует двусвязный список
2. LRU Cache — быстрые операции добавления/удаления
3. Текстовые редакторы — удаление/вставка с отменой
4. Undo/Redo — навигация в обе стороны
5. Плейлист — forward/backward навигация

Полезные советы

1. Всегда проверяй границы — nullptr при пустом списке
2. Освобождай память — используй delete для каждого узла
3. Используй std::list — в реальном коде вместо реализации с нуля
4. Помни о выравнивании — sizeof(Node) может быть больше суммы полей

Двусвязный список — важная структура данных, позволяющая эффективно работать с динамическими наборами данных. Отличается от массива O(1) операциями добавления/удаления, но медленнее на доступе по индексу.