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

1️⃣ Как кратко ответить

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

2️⃣ Подробное объяснение темы

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

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

Каждый узел в двусвязном списке обычно представлен структурой или классом в C++. Рассмотрим пример:

struct Node {
    int data; // Данные, которые хранит узел
    Node* next; // Указатель на следующий узел
    Node* prev; // Указатель на предыдущий узел
​
    // Конструктор для удобного создания узла
    Node(int value) : data(value), next(nullptr), prev(nullptr) {}
};

• int data; — это поле для хранения данных. В данном примере это целое число, но может быть любым типом данных или даже пользовательским объектом.
• Node* next; — указатель на следующий узел в списке. Если узел последний, то next будет указывать на nullptr.
• Node* prev; — указатель на предыдущий узел в списке. Если узел первый, то prev будет указывать на nullptr.
• Конструктор Node(int value) инициализирует узел, устанавливая значение данных и обнуляя указатели.

Пример использования

Создадим простой двусвязный список с тремя элементами:

int main() {
    // Создаем три узла
    Node* first = new Node(1);
    Node* second = new Node(2);
    Node* third = new Node(3);
​
    // Устанавливаем связи между узлами
    first->next = second; // Первый узел указывает на второй
    second->prev = first; // Второй узел указывает на первый
    second->next = third; // Второй узел указывает на третий
    third->prev = second; // Третий узел указывает на второй
​
    // Теперь у нас есть двусвязный список: first <-> second <-> third
​
    // Освобождаем память
    delete first;
    delete second;
    delete third;
​
    return 0;
}

• Создаются три узла: first, second и third, каждый из которых хранит целое число.
• Устанавливаются указатели next и prev для связи узлов в двусвязный список.
• first->next = second; связывает первый узел со вторым.
• second->prev = first; связывает второй узел с первым.
• second->next = third; связывает второй узел с третьим.
• third->prev = second; связывает третий узел со вторым.

Применение

Двусвязные списки полезны, когда требуется частое добавление и удаление элементов с обеих сторон списка или когда необходимо перемещаться в обоих направлениях. Они часто используются в реализации более сложных структур данных, таких как деки и списки в стандартной библиотеке C++.