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

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

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

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

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

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

Каждый узел двунаправленного списка состоит из трех частей:

• Данные: Хранят значение, которое представляет узел.
• Указатель на следующий узел: Ссылка на следующий элемент в списке.
• Указатель на предыдущий узел: Ссылка на предыдущий элемент в списке.

Пример кода

#include <iostream>
​
// Определение структуры узла двунаправленного списка
struct Node {
    int data; // Данные узла
    Node* next; // Указатель на следующий узел
    Node* prev; // Указатель на предыдущий узел
​
    // Конструктор для удобного создания узла
    Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};
​
// Функция для добавления узла в начало двунаправленного списка
void push(Node** head_ref, int new_data) {
    // Создаем новый узел
    Node* new_node = new Node(new_data);
​
    // Устанавливаем следующий узел как текущий head
    new_node->next = (*head_ref);
​
    // Устанавливаем предыдущий узел как nullptr, так как это новый head
    new_node->prev = nullptr;
​
    // Если список не пуст, устанавливаем предыдущий узел текущего head как новый узел
    if ((*head_ref) != nullptr) {
        (*head_ref)->prev = new_node;
    }
​
    // Перемещаем head на новый узел
    (*head_ref) = new_node;
}
​
// Функция для печати двунаправленного списка
void printList(Node* node) {
    Node* last;
    std::cout << "Traversal in forward direction: ";
    while (node != nullptr) {
        std::cout << node->data << " ";
        last = node;
        node = node->next;
    }
    std::cout << std::endl;
​
    std::cout << "Traversal in reverse direction: ";
    while (last != nullptr) {
        std::cout << last->data << " ";
        last = last->prev;
    }
    std::cout << std::endl;
}
​
int main() {
    Node* head = nullptr;
​
    // Добавляем элементы в список
    push(&head, 2);
    push(&head, 4);
    push(&head, 8);
    push(&head, 10);
​
    // Печатаем список
    printList(head);
​
    return 0;
}

Объяснение кода

1. Структура Node: Определяет узел двунаправленного списка с данными и двумя указателями: next и prev.

2. Функция push: Добавляет новый узел в начало списка.

   • Создает новый узел с заданными данными.
   • Устанавливает next нового узла на текущий head.
   • Устанавливает prev нового узла на nullptr, так как это новый head.
   • Если список не пуст, обновляет prev текущего head на новый узел.
   • Обновляет head на новый узел.

3. Функция printList: Печатает список в прямом и обратном порядке.

   • Перемещается по списку от head до конца, выводя данные.
   • Затем перемещается в обратном направлении, начиная с последнего узла.

Применение

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