Мы используем куки, чтобы пользоваться сайтом было удобно.
Хорошо
to the top
close form

Заполните форму в два простых шага ниже:

Ваши контактные данные:

Шаг 1
Поздравляем! У вас есть промокод!

Тип желаемой лицензии:

Шаг 2
Team license
Enterprise license
** Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности
close form
Запросите информацию о ценах
Новая лицензия
Продление лицензии
--Выберите валюту--
USD
EUR
RUB
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
Бесплатная лицензия PVS‑Studio для специалистов Microsoft MVP
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
Для получения лицензии для вашего открытого
проекта заполните, пожалуйста, эту форму
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
Мне интересно попробовать плагин на:
* Нажимая на кнопку, вы даете согласие на обработку
своих персональных данных. См. Политику конфиденциальности

close form
check circle
Ваше сообщение отправлено.

Мы ответим вам на


Если вы так и не получили ответ, пожалуйста, проверьте, отфильтровано ли письмо в одну из следующих стандартных папок:

  • Промоакции
  • Оповещения
  • Спам

Вебинар: Парсим С++ - 25.10

>
>
>
Реализация односвязного списка на C++

Реализация односвязного списка на C++

21 Июн 2023

Список — это структура данных, хранящая элементы в линейном порядке и позволяющая эффективно вставлять и удалять элементы в любом месте последовательности. Списки бывают односвязными и двусвязными. В данной статье реализуем односвязный список на C++. Полный код можно посмотреть здесь.

Основные классы

single_linked_list

Списком будет класс 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 &;
  // ....

node

Односвязный список состоит из узлов. В каждом узле хранится указатель на следующий узел и сами данные:

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_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)

Следующие комментарии next comments
close comment form