Что такое двусвязный список

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

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

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

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

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

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

Применение

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

Пример кода

Рассмотрим пример реализации двусвязного списка на C++:

#include <iostream>
​
// Определение структуры узла двусвязного списка
struct Node {
    int data; // Данные, хранящиеся в узле
    Node* next; // Указатель на следующий узел
    Node* prev; // Указатель на предыдущий узел
​
    // Конструктор для удобного создания узла
    Node(int value) : data(value), next(nullptr), prev(nullptr) {}
};
​
// Класс для управления двусвязным списком
class DoublyLinkedList {
private:
    Node* head; // Указатель на первый узел списка
    Node* tail; // Указатель на последний узел списка
​
public:
    // Конструктор инициализирует пустой список
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}
​
    // Метод для добавления элемента в конец списка
    void append(int value) {
        Node* newNode = new Node(value); // Создаем новый узел
        if (!head) { // Если список пуст
            head = tail = newNode; // Новый узел становится и головой, и хвостом
        } else {
            tail->next = newNode; // Устанавливаем новый узел как следующий для текущего хвоста
            newNode->prev = tail; // Устанавливаем текущий хвост как предыдущий для нового узла
            tail = newNode; // Обновляем хвост
        }
    }
​
    // Метод для удаления элемента с конца списка
    void removeLast() {
        if (!tail) return; // Если список пуст, ничего не делаем
        Node* temp = tail; // Временная переменная для хранения текущего хвоста
        tail = tail->prev; // Перемещаем хвост на предыдущий узел
        if (tail) {
            tail->next = nullptr; // Удаляем ссылку на удаляемый узел
        } else {
            head = nullptr; // Если список стал пустым, обнуляем голову
        }
        delete temp; // Удаляем узел из памяти
    }
​
    // Метод для вывода списка
    void display() const {
        Node* current = head; // Начинаем с головы списка
        while (current) { // Пока не достигнем конца списка
            std::cout << current->data << " "; // Выводим данные текущего узла
            current = current->next; // Переходим к следующему узлу
        }
        std::cout << std::endl; // Завершаем вывод
    }
};
​
int main() {
    DoublyLinkedList list; // Создаем экземпляр двусвязного списка
    list.append(10); // Добавляем элемент 10
    list.append(20); // Добавляем элемент 20
    list.append(30); // Добавляем элемент 30
    list.display(); // Выводим список: 10 20 30
​
    list.removeLast(); // Удаляем последний элемент
    list.display(); // Выводим список: 10 20
​
    return 0;
}

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

• Node: Структура, представляющая узел списка. Содержит данные и два указателя: next и prev.
• DoublyLinkedList: Класс, управляющий двусвязным списком. Содержит указатели на head и tail списка.
• append: Метод добавляет новый узел в конец списка. Если список пуст, новый узел становится и головой, и хвостом. В противном случае, обновляются указатели next и prev.
• removeLast: Метод удаляет последний узел списка. Если список пуст, метод ничего не делает. В противном случае, обновляется указатель tail и удаляется узел из памяти.
• display: Метод выводит все элементы списка, начиная с головы.

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