Мы используем куки, чтобы пользоваться сайтом
было удобно.
Список — это структура данных, хранящая элементы в линейном порядке и позволяющая эффективно вставлять и удалять элементы в любом месте последовательности. Списки бывают односвязными и двусвязными. В данной статье реализуем двусвязный список на C++. Полный код можно посмотреть здесь.
Списком будет класс double_linked_list с одним шаблонным параметром Item — типом хранимых элементов. Это основной класс, содержащий всю логику. Объявляем псевдонимы, необходимые для того, чтобы с нашим списком могли работать функции стандартной библиотеки.
template <typename Item>
class double_linked_list
{
public:
using value_type = Item;
using size_type = size_t;
using difference_type = ptrdiff_t;
using pointer = value_type *;
using const_pointer = const value_type *;
using reference = value_type &;
using const_reference = const value_type &;Двусвязный список состоит из узлов. В каждом узле хранится указатель на следующий узел, указатель на предыдущий узел и сами данные:
private:
struct node
{
node *next = nullptr;
node *prev = nullptr;
value_type data;
node(value_type item) noexcept
: data { std::move(item) }
{
}
};У списка есть два приватных поля — указатели на первый и последний узел списка. Указатель на последний узел списка нужно хранить для быстрой вставки в конец списка:
private:
node *m_head = nullptr;
node *m_tail = nullptr;Добавим ещё два класса — double_linked_list_const_iterator и double_linked_list_iterator. Это итераторы для нашего двусвязного списка. Более подробно познакомиться с концепцией итераторов можно здесь. Реализуем итератор как обёртку над указателем на узел списка. Тип double_linked_list_iterator будет позволять модифицировать элемент, на который он указывает, а double_linked_list_const_iterator — нет:
public:
class double_linked_list_const_iterator
{
private:
explicit double_linked_list_const_iterator(const node *ptr)
noexcept
: m_current { ptr }
{
}
friend class double_linked_list;
public:
using difference_type = double_linked_list::difference_type;
using value_type = double_linked_list::value_type;
using pointer = double_linked_list::const_pointer;
using reference = double_linked_list::const_reference;
using iterator_category = std::bidirectional_iterator_tag;
reference operator*() const noexcept
{
assert(m_current != nullptr);
return m_current->data;
}
double_linked_list_const_iterator& operator++() noexcept
{
assert(m_current != nullptr);
m_current = m_current->next;
return *this;
}
double_linked_list_const_iterator& operator--() noexcept
{
assert(m_current != nullptr);
m_current = m_current->prev;
return *this;
}
double_linked_list_const_iterator operator++(int) noexcept
{
assert(m_current != nullptr);
auto copy = *this;
m_current = m_current->next;
return copy;
}
double_linked_list_const_iterator operator--(int) noexcept
{
assert(m_current != nullptr);
auto copy = *this;
m_current = m_current->prev;
return copy;
}
bool operator==(double_linked_list_const_iterator other)
const noexcept
{
return m_current == other.m_current;
}
bool operator!=(double_linked_list_const_iterator other)
const noexcept
{
return !(*this == other);
}
protected:
const node *Get() const noexcept
{
return m_current;
}
protected:
const node *m_current;
};
class double_linked_list_iterator
: public double_linked_list_const_iterator
{
private:
friend class double_linked_list;
explicit double_linked_list_iterator(node *ptr) noexcept
: double_linked_list_const_iterator { ptr }
{
}
public:
using difference_type = double_linked_list::difference_type;
using value_type = double_linked_list::value_type;
using pointer = double_linked_list::pointer;
using reference = double_linked_list::reference;
using iterator_category = std::bidirectional_iterator_tag;
reference operator*() noexcept
{
return const_cast<reference>(
double_linked_list_const_iterator::operator*()
);
}
double_linked_list_iterator& operator++() noexcept
{
double_linked_list_const_iterator::operator++();
return *this;
}
double_linked_list_iterator& operator--() noexcept
{
double_linked_list_const_iterator::operator--();
return *this;
}
double_linked_list_iterator operator++(int) noexcept
{
auto res = double_linked_list_const_iterator::operator++(0);
return double_linked_list_iterator {
const_cast<node *>(res.Get())
};
}
double_linked_list_iterator operator--(int) noexcept
{
auto res = double_linked_list_const_iterator::operator--(0);
return double_linked_list_iterator {
const_cast<node *>(res.Get())
};
}
};Тип double_linked_list_const_iterator содержит стандартные для итератора операторы сравнения, инкремента, декремента и разыменования. В double_linked_list_iterator добавим перегрузку оператора разыменования, возвращающую неконстантную ссылку на элемент, чтобы его можно было модифицировать. Также добавим свои перегрузки операторов инкремента/декремента, чтобы они возвращали итераторы на неконстантный элемент.
В классе double_linked_list_const_iterator реализован метод Get, возвращающий сырой указатель. Этот метод будет нужен для операций над списком, модифицирующих указатели, лежащие внутри узлов и спрятанные от пользователя. Делаем его protected, чтобы пользователь класса не мог напрямую его вызвать, и объявляем класс double_linked_list_const_iterator friend-ом класса double_linked_list, чтобы иметь доступ к методу Get в методах класса double_linked_list.
Также объявляем псевдонимы const_iterator и iterator:
using iterator = double_linked_list_iterator;
using const_iterator = double_linked_list_iterator;Конструктор пустого списка:
double_linked_list() = default;Конструировать список можно из std::initializer_list. Реализуем конструктор следующим образом — создаём пустой список и последовательно вставляем в его конец элементы:
double_linked_list(std::initializer_list<value_type> items)
{
for (auto &item : items)
{
push_back(item);
}
}Функция вставки элемента в конец push_back реализована в следующем разделе.
Реализуем функцию clear, удаляющую все узлы списка. Деструктор списка просто вызывает функцию clear:
~double_linked_list()
{
clear();
}
void clear() noexcept
{
while (m_head)
{
delete std::exchange(m_head, m_head->next);
}
m_tail = nullptr;
}Для вставки элементов в список будем предоставлять три функции: push_front, push_back и insert.
Функция push_front принимает один аргумент — новый элемент item — и вставляет его в начало списка:
void push_front(value_type item)
{
auto newnode = new node { std::move(item) };
if (m_head)
{
m_head->prev = newnode;
newnode->next = m_head;
m_head = newnode;
}
else
{
m_head = m_tail = newnode;
}
}Функция push_back принимает один аргумент — новый элемент item — и вставляет его в конец списка. В нашей реализации в списке хранится указатель на последний узел, используем его, чтобы избежать полного обхода списка:
void push_back(value_type item)
{
auto newnode = new node { std::move(item) };
if (m_tail)
{
m_tail->next = newnode;
newnode->prev = m_tail;
m_tail = newnode;
}
else
{
m_head = m_tail = newnode;
}
}Обратите внимание на проверку if (m_tail). Отсутствие этой проверки приведёт к segmentation fault при вызове этого метода на пустом списке. В непустом списке будет хотя бы один узел, а значит, указатель m_tail будет ненулевым. В этом случае выполняется then-ветка, и новый узел будет "присоединён" к последнему элементу старого списка с помощью обновления указателей.
Если же список был пустой, то и указатель m_tail был нулевым. В таком случае выполняется else-ветка и новый узел становится одновременно и первым, и последним узлом списка.
Функция insert принимает два аргумента: итератор place на уже существующий узел списка и новый элемент item, и вставляет item перед узлом place. Для этого достаточно создать новый узел и обновить значение 4 указателей.
void insert(const_iterator place, value_type item)
{
auto ptr = const_cast<node *>(place.Get());
if (!ptr)
{
push_back(std::move(item));
return;
}
auto newnode = new node { std::move(item) };
newnode->next = ptr;
newnode->prev = ptr->prev;
if (ptr->prev)
{
ptr->prev->next = newnode;
}
ptr->prev = newnode;
}Если в функцию передать нулевой указатель (эквивалентен итератору end), то новый элемент будет добавлен в конец списка.
Для обхода списка у нас уже есть итераторы. Для того, чтобы список можно было обходить range-based for циклом, нужно реализовать методы begin и end. Реализуем const и не const-версии:
const_iterator begin() const noexcept
{
return const_iterator { m_head };
}
const_iterator end() const noexcept
{
return const_iterator { nullptr };
}
const_iterator cbegin() const noexcept
{
return const_iterator { m_head };
}
const_iterator cend() const noexcept
{
return const_iterator { nullptr };
}
iterator begin() noexcept
{
return iterator { m_head };
}
iterator end() noexcept
{
return iterator { nullptr };
}Теперь список можно обходить циклом for:
void foo()
{
DoubleLinkedList<int> l {1, 2, 3};
for (auto item : l)
{
// do smth
}
}Для поиска элементов в списке реализуем метод find, принимающий элемент для поиска и возвращающий итератор на узел с искомым элементом. Для поиска просто обходим список и сравниваем данные в текущем узле с искомыми. Реализуем const и не const-версии:
const_iterator find(const_reference item) const noexcept
{
for (auto it = begin(); it != end(); ++it)
{
if (*it == item)
{
return it;
}
}
return const_iterator { nullptr };
}
iterator find(const_reference item) noexcept
{
auto it = static_cast<const double_linked_list &>(*this)
.find(item);
return iterator { const_cast<node *>(it.Get()) };
}Для удаления элементов реализуем функцию erase, принимающую итератор на узел и удаляющую его. Для удаления узла нужно обновить указатель next у предыдущего узла списка и обновить указатель prev у следующего узла:
void erase(const_iterator place) noexcept
{
auto ptr = const_cast<node *>(place.Get());
assert(ptr != nullptr);
if (ptr->prev)
{
ptr->prev->next = ptr->next;
}
else
{
m_head = ptr->next;
}
if (ptr->next)
{
ptr->next->prev = ptr->prev;
}
else
{
m_tail = ptr->prev;
}
delete ptr;
}При удалении узла из двусвязного списка возможны несколько случаев.
Во-первых, у узла могут быть оба соседа: предыдущий узел и следующий узел. Тогда в обоих if будут выполнены then-ветки и будут обновлены соответствующие указатели у этих узлов.
Во-вторых, у узла может быть только один сосед — следующий узел. Это означает, что удаляемый узел — первый узел в списке, состоящем из минимум 2 узлов. В таком случае в первом if выполнится else-ветка и будет обновлено поле m_first. Во втором if выполнится then-ветка и будет обновлен указатель у соседнего узла.
В-третьих, у узла может быть только один сосед — предыдущий узел. Это означает, что удаляемый узел — последний в списке, состоящем из минимум 2 узлов. В таком случае в первом if выполнится then-ветка и будет обновлен указатель у соседнего узда. Во втором if выполнится else-ветка и будет обновлено поле m_last.
В-четвертых, узел может не иметь соседних узлов. Это означает, что удаляемый узел — единственный узел списка. В таком случае в обоих if будут выполнены then-ветки и поля m_first и m_last будут равны нулевому указателю.
Мы изучили сайт Stack Overflow, чтобы понять, с какими ошибками чаще всего сталкиваются люди при попытке реализовать списки. Рассмотрим несколько типовых ошибок.
Работа со списками влечёт за собой работу с указателями, и ошибиться легко. Например, можно случайно разыменовать нулевой указатель:
void insert(const_iterator place, value_type item)
{
auto ptr = const_cast<node *>(place.Get());
if (!ptr)
{
push_back(std::move(item));
}
auto newnode = new node { std::move(item) };
newnode->next = ptr;
newnode->prev = ptr->prev;
if (ptr->prev)
{
ptr->prev->next = newnode;
}
ptr->prev = newnode;
}Предлагаю вам поискать ошибку самим и засечь время, за которое вы её обнаружите.
Нашли? Тогда давайте вместе проверим. В данном фрагменте кода возможно разыменование нулевого указателя ptr. Рассмотрим, что произойдёт, если в функцию insert передадут нулевой указатель ptr. В коде есть проверка if (!ptr). Однако в then-ветке забыли написать return. Поэтому после вызова функции push_back выполнение тела функции insert продолжится. Будет выполнено вычисление выражение ptr->next и произойдёт разыменование нулевого указателя.
Найти эту ошибку можно проще. Достаточно зайти на сайт Compiler Explorer. На нём выбираем язык С++, на source вкладке вставляем свой код. Выбираем компилятор на свой вкус и на вкладке "компилятор" жмём кнопку AddTool. В выпавшем списке выбираем PVS-Studio. Теперь ваш код проверится статическим анализатором кода PVS-Studio. Такой способ отлично подходит при написании лабораторных и курсовых работ. Вот что выдаёт PVS-Studio на разобранном примере:
<source>:187:1: warning: V1004 The 'ptr' pointer was used unsafely after it was verified against nullptr. Check lines: 179, 187.
187 — это номер строки, в которой возможно разыменование. Давайте взглянем на эту строку:
newnode->prev = ptr->prev;Отлично, осталось лишь посмотреть чуть выше по коду и понять, почему этот указатель может быть нулевым. Так гораздо лучше, чем самому пересматривать весь код целиком.
В данной статье мы разобрали, как реализовать двусвязный список на языке C++. Хорошим помощником при изучении программирования и выполнении лабораторных работ может стать сочетание Compiler Explorer и PVS-Studio.
Compiler Explorer позволяет проводить эксперименты с кодом прямо в браузере. PVS-Studio, встроенный в Compiler Explorer, поможет быстро найти многие ошибки. См. статью: Тем, кто учится программировать и решил написать вопрос на Stack Overflow: "Почему код не работает?".
0
0
0
Мы ответим вам на
Если вы так и не получили ответ, пожалуйста, проверьте, отфильтровано ли письмо в одну из следующих стандартных папок:
0