Мы используем куки, чтобы пользоваться сайтом
было удобно.
Список — это структура данных, хранящая элементы в линейном порядке и позволяющая эффективно вставлять и удалять элементы в любом месте последовательности. Списки бывают односвязными и двусвязными. В данной статье реализуем односвязный список на C++. Полный код можно посмотреть здесь.
Списком будет класс single_linked_list с одним шаблонным параметром Item — типом хранимых элементов. Это основной класс, содержащий всю логику. Для начала объявим псевдонимы, необходимые для того, чтобы с нашим списком могли работать функции стандартной библиотеки.
template <typename Item>
class single_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;
Item data;
node(value_type item) noexcept
: data { std::move(item) }
{
};
};У списка есть два приватных поля — указатели на первый и последний узел списка. Указатель на последний узел списка нужно хранить для быстрой вставки в конец списка.
private:
node *m_head = nullptr;
node *m_tail = nullptr;Добавим ещё два класса — single_linked_list_const_iterator и single_linked_list_iterator. Это итераторы для нашего односвязного списка. Более подробно познакомиться с концепцией итераторов можно здесь. Реализуем итератор как обёртку над указателем на узел списка. Объект single_linked_list_iterator позволит модифицировать элемент, на который он указывает, а single_linked_list_const_iterator — нет:
public:
class single_linked_list_const_iterator
{
private:
friend class single_linked_list;
explicit single_linked_list_const_iterator(const node *ptr) noexcept
: m_current{ ptr }
{
}
public:
using difference_type = single_linked_list::difference_type;
using value_type = single_linked_list::value_type;
using pointer = single_linked_list::const_pointer;
using reference = single_linked_list::const_reference;
using iterator_category = std::forward_iterator_tag;
reference operator*() const noexcept
{
assert(m_current != nullptr);
return m_current->data;
}
single_linked_list_const_iterator& operator++() noexcept
{
assert(m_current != nullptr);
m_current = m_current->next;
return *this;
}
single_linked_list_const_iterator operator++(int) noexcept
{
assert(m_current != nullptr);
auto copy = *this;
m_current = m_current->next;
return copy;
}
bool operator==(single_linked_list_const_iterator other)
const noexcept
{
return m_current == other.m_current;
}
bool operator!=(single_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 single_linked_list_iterator : public single_linked_list_const_iterator
{
private:
friend class single_linked_list;
explicit single_linked_list_iterator(node *ptr) noexcept
: single_linked_list_const_iterator { ptr }
{
}
public:
using difference_type = single_linked_list::difference_type;
using value_type = single_linked_list::value_type;
using pointer = single_linked_list::pointer;
using reference = single_linked_list::reference;
using iterator_category = std::forward_iterator_tag;
reference operator*() noexcept
{
auto &&res = single_linked_list_const_iterator::operator*();
return const_cast<reference>(res);
}
single_linked_list_iterator& operator++() noexcept
{
single_linked_list_const_iterator::operator++();
return *this;
}
single_linked_list_iterator operator++(int) noexcept
{
auto res = single_linked_list_const_iterator::operator++(0);
return single_linked_list_iterator {
const_cast<node *>(res.Get())
};
}
};Тип single_linked_list_const_iterator содержит стандартные для итератора операторы сравнения, инкремента и разыменования. В single_linked_list_iterator добавим перегрузку оператора разыменования, возвращающую неконстантную ссылку на элемент, чтобы его можно было модифицировать. Также добавим свои перегрузки операторов инкремента, чтобы они возвращали итераторы на неконстантный элемент.
Помимо этого, в классе single_linked_list_const_iterator реализована функция Get, возвращающая "сырой" указатель. Эта функция будет нужна для операций над списком, модифицирующих указатели, лежащие внутри узлов и спрятанные от пользователя. Делаем его protected, чтобы пользователь класса не мог напрямую его вызвать, и объявляем класс single_linked_list_const_iterator другом класса single_linked_list, чтобы иметь доступ к функции Get в функциях класса single_linked_list.
Также объявляем псевдонимы const_iterator и iterator:
using iterator = single_linked_list_iterator;
using const_iterator = single_linked_list_const_iterator;Конструктор пустого списка:
single_linked_list() = default;Конструировать список можно также из std::initializer_list. Реализуем конструктор следующим образом — создаём пустой список и последовательно вставляем в его конец элементы:
single_linked_list(std::initializer_list<Item> items)
{
for (auto &item : items)
{
push_back(item);
}
}Функция вставки элемента в конец push_back реализована в следующем разделе.
Реализуем функцию clear, удаляющую все узлы списка. Деструктор списка просто вызывает функцию clear:
~single_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_after.
Функция push_front принимает один аргумент — новый элемент item — и вставляет его в начало списка:
void push_front(value_type item)
{
auto newnode = new node { std::move(item) };
if (m_head)
{
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;
m_tail = newnode;
}
else
{
m_head = m_tail = newnode;
}
}Обратите внимание на проверку if (m_tail). Отсутствие этой проверки приведёт к segmentation fault при вызове этой функции на пустом списке. В непустом списке будет хотя бы один узел, а значит, указатель m_tail будет ненулевым. В этом случае выполняется then-ветка, и новый узел будет "присоединён" к последнему элементу старого списка с помощью обновления указателя.
Если же список был пустой, то и указатель m_tail был нулевым. В таком случае выполняется else-ветка, и новый узел становится одновременно и первым, и последним узлом списка.
Функция insert_after принимает два аргумента: итератор place на уже существующий узел списка и новый элемент item, и вставляет item после узла place. Если передать в метод невалидный итератор (нулевой указатель) в качестве place, то новый узел вставится в начало списка:
void insert_after(const_iterator place, value_type item)
{
auto ptr = const_cast<node *>(place.Get());
if (!ptr)
{
push_front(std::move(item));
return;
}
auto newnode = new node { std::move(item) };
newnode->next = ptr->next;
ptr->next = newnode;
}Для обхода списка у нас уже есть итераторы. Для того чтобы список можно было обходить 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 };
}Теперь список можно обходить в цикле вот так:
void foo()
{
single_linked_list<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 single_linked_list &>(*this).find(item);
return { const_cast<node *>(it.Get()) };
}Для удаления элементов реализуем функцию erase_after, принимающую итератор на узел и удаляющий следующий после него узел. Для удаления узла нужно обновить указатель next у переданного узла списка. Если передать в метод невалидный указатель (нулевой указатель), то будет удалён первый узел списка.
void erase_after(const_iterator place) noexcept
{
auto ptr = const_cast<node *>(place.Get());
if (ptr)
{
auto nodeToDelete = ptr->next;
if (ptr->next)
{
ptr->next = ptr->next->next;
}
delete nodeToDelete;
}
else
{
assert(m_head != nullptr);
delete std::exchange (m_head, m_head->next);
}
}Мы изучили сайт Stack Overflow, чтобы понять, с какими ошибками чаще всего сталкиваются людипри попытке реализовать списки. Рассмотрим несколько типовых ошибок.
Работа со списками влечёт за собой работу с указателями, и ошибиться легко. Например, можно случайно разыменовать нулевой указатель:
void insert_after(const_iterator place, value_type item)
{
auto ptr = const_cast<node *>(place.Get());
if (!ptr)
{
push_front(std::move(item));
}
auto newnode = new node { std::move(item) };
newnode->next = ptr->next;
ptr->next = newnode;
}Предлагаю вам поискать ошибку самим и засечь время, за которое вы её обнаружите.
Нашли? Тогда давайте вместе проверим. В данном фрагменте кода возможно разыменование нулевого указателя ptr. Рассмотрим, что произойдёт, если в функцию insert_after передадут нулевой указатель ptr. В коде есть проверка if (!ptr). Однако в then-ветке забыли написать return. Поэтому после вызова функции push_back выполнение тела функции insert продолжится. Будет выполнено вычисление выражение ptr->next и произойдёт разыменование нулевого указателя.
Найти эту ошибку можно проще. Достаточно зайти на сайт Compiler Explorer. На нём выбираем язык С++, на source вкладке вставляем свой код. Выбираем компилятор на свой вкус и на вкладке "компилятор" жмём кнопку AddTool. В выпавшем списке выбираем PVS-Studio. Теперь ваш код проверится статическим анализатором кода PVS-Studio. Такой способ отлично подходит при написании лабораторных и курсовых работ. Вот что выдаёт PVS-Studio на разобранном примере:
<source>:166:1: warning: V1004 The 'ptr' pointer was used unsafely after it was verified against nullptr. Check lines: 160, 166.
166 — это номер строки, в которой возможно разыменование. Давайте взглянем на эту строку:
newnode->next = ptr->next;Отлично, осталось лишь посмотреть чуть выше по коду и понять, почему этот указатель может быть нулевым. Так гораздо лучше, чем самому пересматривать весь код целиком.
В данной статье мы разобрали, как реализовать односвязный список на языке C++. Хорошим помощником при изучении программирования и выполнении лабораторных работ может стать сочетание Compiler Explorer и PVS-Studio.
Compiler Explorer позволяет проводить эксперименты с кодом прямо в браузере. PVS-Studio, встроенный в Compiler Explorer, поможет быстро найти многие ошибки.
См. статью: Тем, кто учится программировать и решил написать вопрос на Stack Overflow: "Почему код не работает?".
0
0
0
Мы ответим вам на
Если вы так и не получили ответ, пожалуйста, проверьте, отфильтровано ли письмо в одну из следующих стандартных папок:
0