Двусвязный список - структура данных, которая состоит из отдельных узлов. Каждый узел хранит собственные данные и два указателя: на предыдущий и на следующий узлы. Последний узел указывает на nullptr, а первый - на "голову" списка - узел, который предшествует первому узлу. Итеррироваться по списку можно как в прямом, так и в обратном направлениях. Узлы хранятся в динамической памяти.
- C++
- STL
- динамическая память
- итераторы
- конструктор по умолчанию, конструктор от std::initializer_list
- конструтор копирования и оператор присваивания
- перемещающий конструктор и перемещающий оператор присваивания
- деструктор
- получение итераторов на начало и конец списка
- добавление элемента в начало списка PushFront (обеспечивает строгую гарантию безопасности)
- добавление элемента в конец списка PushBack (обеспечивает строгую гарантию безопасности)
- удаление первого элемента PopFront
- удаление последнего элемента PopBack
- получение первого элемента списка front
- получение последнего элемента списка back
- метод Size, который возвращает количесво элементов в списке
- метод IsEmpty, который опредделяет пуст ли список
- метод swap для обмена элементами между списками
- метод очистки списка Clear, не бросающий исключений
- метод reverse для разворота списка задом наперёд
- добавление элемента в середину и конец списка InsertAfter
- удаление элемента из середины и конца списка EraseAfter
- операции сравнения списков <, >, <=, >=, ==, !=
- вставка, удаление элемента, операция swap, перемещение списка выполняются за константное время О(1)
- элементы хранятся в динамической памяти и выделение/удаление памяти требует определённого времени
- элементы в памяти хранятся непоследовательно из-за этого затруднено кэширование
- перебор элементов в двух направлениях
- обращение к n-ному элементу осуществляется за время О(n)
Для использования в своих проектах:
- Скачайте файл double-linked-list.h
- Поместите его в каталог своего проекта
- Подключите с помощью директивы #include "double-linked-list.h"
Компилятор С++, С++17