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

[Список](https://pvs-studio.ru/ru/blog/terms/6681/) — это структура данных, хранящая элементы в линейном порядке и позволяющая эффективно вставлять и удалять элементы в любом месте последовательности\. Списки бывают односвязными и двусвязными\. В данной статье реализуем двусвязный список на C\+\+\. Полный код можно посмотреть [здесь](https://godbolt.org/z/7TGP6nncf)\.

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

### double\_linked\_list

Списком будет класс _double\_linked\_list_ с одним шаблонным параметром _Item_ — типом хранимых элементов\. Это основной класс, содержащий всю логику\. Объявляем псевдонимы, необходимые для того, чтобы с нашим списком могли работать функции стандартной библиотеки\.

```cpp
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 &;
```

### node

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

```cpp
private:
  struct node
  {
    node *next = nullptr;
    node *prev = nullptr;
    value_type data;

    node(value_type item) noexcept
      : data { std::move(item) }
    {
    }
  };
```

У списка есть два приватных поля — указатели на первый и последний узел списка\. Указатель на последний узел списка нужно хранить для быстрой вставки в конец списка:

```cpp
private:
  node *m_head = nullptr;
  node *m_tail = nullptr;
```

### double\_linked\_list\_const\_iterator и double\_linked\_list\_iterator

Добавим ещё два класса — _double\_linked\_list\_const\_iterator_ и _double\_linked\_list\_iterator_\. Это итераторы для нашего двусвязного списка\. Более подробно познакомиться с концепцией итераторов можно [здесь](https://pvs-studio.ru/ru/blog/terms/6540/)\. Реализуем итератор как обёртку над указателем на узел списка\. Тип _double\_linked\_list\_iterator_ будет позволять модифицировать элемент, на который он указывает, а _double\_linked\_list\_const\_iterator _— нет:

```cpp
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_:

```cpp
  using iterator       = double_linked_list_iterator;
  using const_iterator = double_linked_list_iterator;
```

## Функции\-члены

### Конструкторы

Конструктор пустого списка:

```cpp
  double_linked_list() = default;
```

Конструировать список можно из _std::initializer\_list_\. Реализуем конструктор следующим образом — создаём пустой список и последовательно вставляем в его конец элементы:

```cpp
  double_linked_list(std::initializer_list<value_type> items)
  {
    for (auto &item : items)
    {
      push_back(item);
    }
  }
```

Функция вставки элемента в конец _push\_back_ реализована в следующем разделе\.

### Деструктор

Реализуем функцию _clear_, удаляющую все узлы списка\. Деструктор списка просто вызывает функцию _clear_:

```cpp
  ~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_ — и вставляет его в начало списка: 

```cpp
  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_ — и вставляет его в конец списка\. В нашей реализации в списке хранится указатель на последний узел, используем его, чтобы избежать полного обхода списка:

```cpp
  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](https://pvs-studio.ru/ru/blog/terms/0063/) при вызове этого метода на пустом списке\. В непустом списке будет хотя бы один узел, а значит, указатель _m\_tail_ будет ненулевым\. В этом случае выполняется _then_\-ветка, и новый узел будет "присоединён" к последнему элементу старого списка с помощью обновления указателей\.

Если же список был пустой, то и указатель _m\_tail_ был нулевым\. В таком случае выполняется _else_\-ветка и новый узел становится одновременно и первым, и последним узлом списка\.

Функция _insert_ принимает два аргумента: итератор _place_ на уже существующий узел списка и новый элемент _item_, и вставляет _item_ перед узлом _place_\. Для этого достаточно создать новый узел и обновить значение 4 указателей\.

```cpp
  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\-версии:

```cpp
  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_:

```cpp
void foo()
{
  DoubleLinkedList<int> l {1, 2, 3};
  for (auto item : l)
  {
    // do smth
  }
}
```

### Поиск

Для поиска элементов в списке реализуем метод _find,_ принимающий элемент для поиска и возвращающий итератор на узел с искомым элементом\. Для поиска просто обходим список и сравниваем данные в текущем узле с искомыми\. Реализуем const и не const\-версии:

```cpp
  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_ у следующего узла:

```cpp
  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, чтобы понять, с какими ошибками чаще всего сталкиваются люди при попытке реализовать списки\. Рассмотрим несколько типовых ошибок\.

### Разыменование нулевого указателя

Работа со списками влечёт за собой работу с указателями, и ошибиться легко\. Например, можно случайно разыменовать нулевой указатель:

```cpp
  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](https://godbolt.org)\. На нём выбираем язык С\+\+, на _source_ вкладке вставляем свой код\. Выбираем компилятор на свой вкус и на вкладке "компилятор" жмём кнопку AddTool\. В выпавшем списке выбираем PVS\-Studio\. Теперь ваш код проверится статическим анализатором кода PVS\-Studio\. Такой способ отлично подходит при написании лабораторных и курсовых работ\. Вот что выдаёт PVS\-Studio на разобранном [примере](https://godbolt.org/z/qWG9azcdn):

<source\>:187:1: warning: V1004 The 'ptr' pointer was used unsafely after it was verified against nullptr\. Check lines: 179, 187\.

187 — это номер строки, в которой возможно разыменование\. Давайте взглянем на эту строку:

```cpp
newnode->prev = ptr->prev;
```

Отлично, осталось лишь посмотреть чуть выше по коду и понять, почему этот указатель может быть нулевым\. Так гораздо лучше, чем самому пересматривать весь код целиком\.

## Вывод

В данной статье мы разобрали, как реализовать двусвязный список на языке C\+\+\. Хорошим помощником при изучении программирования и выполнении лабораторных работ может стать сочетание [Compiler Explorer](https://godbolt.org/) и [PVS\-Studio](https://pvs-studio.ru/ru/pvs-studio/)\.

Compiler Explorer позволяет проводить эксперименты с кодом прямо в браузере\. PVS\-Studio, встроенный в Compiler Explorer, поможет быстро найти многие ошибки\. См\. статью: [Тем, кто учится программировать и решил написать вопрос на Stack Overflow: "Почему код не работает?"](https://pvs-studio.ru/ru/blog/posts/cpp/0959/)\.

## Дополнительные ссылки

* [Список](https://pvs-studio.ru/ru/blog/terms/6681/)
* [Реализация двусвязного списка на C](https://pvs-studio.ru/ru/blog/terms/6682/)
* [Реализация односвязного списка на C](https://pvs-studio.ru/ru/blog/terms/6680/)
* [Реализация односвязного списка на C\+\+](https://pvs-studio.ru/ru/blog/terms/6684/)