# Implementation of a doubly linked list in C\+\+

A [list](https://pvs-studio.com/en/blog/terms/6681/) is a linear collection of data that allows you to efficiently insert and delete elements from any point in the list\. Lists can be singly linked and doubly linked\. In this article, we will implement a doubly linked list in C\+\+\. The full code is [here](https://godbolt.org/z/7TGP6nncf)\.

## Main classes

### double\_linked\_list

A list would be the _double\_linked\_list_ class with one _Item_ template parameter \(the type of stored elements\)\. This is the main class that contains all the logic\. We declare the aliases required for the standard library functions to work with our list\.

```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

A doubly linked list consists of nodes\. Each node contains a pointer to the next node, a pointer to the previous node, and the data:

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

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

The list has two private fields, these are the pointers to the first and to the last node\. The pointer to the last node should be saved for quick insertion at the end of the list:

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

### double\_linked\_list\_const\_iterator and double\_linked\_list\_iterator

Let's add two more classes — _double\_linked\_list\_const\_iterator_ and _double\_linked\_list\_iterator_\. These are iterators for our doubly linked list\. [Here](https://pvs-studio.com/en/blog/terms/6540/) you can learn more about iterators\. We implement the iterator as a wrapper around a pointer to a node\. The _double\_linked\_list\_iterator_ type allows you to modify the element it points to, but _double\_linked\_list\_const\_iterator_ does not:

```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())
      };
    }
  };
```

The _double\_linked\_list\_const\_iterator_ type contains comparison, increment, decrement, and dereference operators that are standard for an iterator\. In _double\_linked\_list\_iterator_, we overload the dereference operator, which returns a non\-const reference to the element so that it can be modified\. We also overload the increment/decrement operators so that they return iterators to a non\-const element\.

In the _double\_linked\_list\_const\_iterator_ class, the _Get_ function that returns a raw pointer is implemented\. This method will be necessary for list operations that modify pointers hidden from users within nodes\. We make the method _protected_ so that the user of the class cannot call it directly\. Then, we declare _the double\_linked\_list\_const\_iterator_ a friend class of _double\_linked\_list_ in order to have access to the _Get_ function in the methods of the _double\_linked\_list_ class\.

Let's declare the _const\_iterator_ and _iterator _aliases:

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

## Member functions

### Constructors

Empty list constructor:

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

You can use _std::initializer\_list_ to create a list\. To implement the constructor, we create an empty list and sequentially insert elements at the end of it:

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

We will explore inserting elements at the end of _push\_back_ below\.

### Destructor

We use the _clear_ function to remove all the nodes of the list\. The list destructor simply calls the _clear_ function:

```cpp
  ~double_linked_list()
  {
    clear();
  }

  void clear() noexcept
  {
    while (m_head)
    {
      delete std::exchange(m_head, m_head->next);
    }

    m_tail = nullptr;
  }
```

### Insertion

We have three functions to insert items to the list: _push\_front, push\_back_, and _insert_\. 

The _push\_front_ function takes one argument \(the new _item_ element\) and inserts it at the beginning of the list: 

```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;
    }
  }
```

The _push\_back_ function takes one argument \(the new _item_ element\) and inserts it at the end of the list\. In this implementation, a pointer to the last node is saved in the list — we will use it to avoid traversing the entire list:

```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;
    }
  }
```

Note the _if \(m\_tail\)_ check\. If we try to call this method in an empty list without the check, a [segmentation fault](https://pvs-studio.com/en/blog/terms/0063/) will occur\. However, a non\-empty list has at least one node, which means the _m\_tail_ pointer will be non\-null\. In this case, the _then_ branch is executed, and the new node will be "attached" to the last element of the old list by updating the pointers\.

If the list is empty, then the _m\_tail_ pointer is null\. In this case, the _else_ branch is executed and the new node becomes both the first and the last node of the list\.

The _insert_ function takes two arguments: the _place_ iterator for the already existing node of the list and the new _item_ element\. The function inserts _item_ before the _place_ node\. To do this, just create a new node and update the values of 4 pointers\.

```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;
  }
```

If we pass a null pointer \(equivalent to the _end_ iterator\) to the function, then the new element will be inserted at the beginning of the list\.

### Traversal

We have iterators to traverse the list\. To traverse it with the _range\-based for_ loop, we need to implement the _begin_ and _end_ functions\. Implementing const and non\-const versions:  

```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 };
  }
```

Now the list can be traversed with the _for_ loop:

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

### Search

We use the _find_ method to search for the elements in the list\. It takes an element to be searched and returns an iterator to the node with the element needed\. To find an element, we traverse the list and compare the data of the current node data with the data we are looking for\. Implementing const and non\-const versions:

```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()) };
  }
```

### Deletion

To delete elements, use the _erase_ function, which takes an iterator to a node and deletes the next node after it\. To delete a node, we update the _next_ pointer of the passed list node and update the _prev_ pointer of the next node:

```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;
  }
```

When deleting a node in a doubly linked list, several cases are possible\.

Firstly, a node can have both neighbors: the previous node and the next node\. Then, in both _if_ statements, _then_ branches are executed and the corresponding pointers to these nodes are updated\.

Secondly, a node can also have only one neighbor — the next node\. This means that the node being deleted is the first node of the list consisting of at least 2 nodes\. In this case, the _else_ branch is executed in the first _if_ statement, and the _m\_first_ field is updated\. In the second _if_, the _then_ branch is executed and the pointer of the next node is updated\.

Thirdly, a node can have only one neighbor — the previous node\. This means that the node being deleted is the last node of the list consisting of at least 2 nodes\. In this case, in the first _if_ statement, the _then_ branch is executed and the pointer of the next node is updated\. In the second _if_, the _else_ branch will be executed and the _m\_last_ field is updated\.

Fourthly, a node may not have neighboring nodes\. This means that the node being deleted is the only node of the list\. In this case, _then_ branches are executed in both _if_ statements, and the _m\_first_ and _m\_last fields_ will be equal to the null pointer\.

## Potential errors and how to avoid them

We researched Stack Overflow for the most common errors users face with when trying to implement lists\. Let's look at some typical errors\.

### Dereferencing a null pointer

It's easy to make mistakes when working with lists and pointers\. For example, we can accidentally dereference a null pointer:

```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;
  }
```

Note the time and see if you can find the error yourself\.

Have you found it? Then let's inspect it together\. In this code fragment, it is possible to dereference the _ptr_ null pointer\. Here is what happens if the _ptr_ null pointer is passed to the _insert_ function\. There is an _if \(\!ptr\)_ check in the code\. However, _return_ is missing in the _then_ branch\. Therefore, after calling the _push\_back_ function, the execution of the _insert_ function body continues\. The _ptr\-\>next_ expression will be evaluated and the null pointer will be dereferenced\.

You can find this error easier\. Just go to the [Compiler Explorer](https://godbolt.org/) website\. Select the C\+\+ language, paste your code in the _source_ tab\. Select a preferable compiler\. On the compiler tab, click AddTool\. Select PVS\-Studio in the drop\-down menu\. Now the PVS\-Studio static code analyzer will check your code\. This approach is great for writing lab reports and term papers\. Here's what PVS\-Studio issues for this [code fragment](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 is the number of the line where dereference is possible\. Let's take a look at this line:

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

Great, all we have to do now is to look at the above code and figure out why this pointer can be null\. This is much better than reviewing the entire code manually\.

## Conclusion

In this article, we have discussed the implementation of a doubly linked list in C\+\+\. With [Compiler Explorer](https://godbolt.org/) and [PVS\-Studio](https://pvs-studio.com/en/pvs-studio/), you can learn programming and write lab reports\.

Compiler Explorer makes it possible to experiment with code right in your web_ _browser\. PVS\-Studio, integrated into Compiler Explorer, will help you quickly find various errors in code\.

See the article: ["Why doesn't my code work?" — to anyone learning the art of programming and writing to the Stack Overflow community](https://pvs-studio.com/en/blog/posts/cpp/0959/)\.

## Additional links

* [List](https://pvs-studio.com/en/blog/terms/6681/)
* [Implementation of a doubly linked list in C](https://pvs-studio.com/en/blog/terms/6682/)
* [Implementation of a singly linked list in C](https://pvs-studio.com/en/blog/terms/6680/)
* [Implementation of a singly linked list in C\+\+](https://pvs-studio.com/en/blog/terms/6684/)