# Implementation of a singly 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 singly linked list in C\+\+\. The full code is [here](https://godbolt.org/z/e8orhjed8)\.

## Main classes

### single\_linked\_list

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

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

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

```cpp
private:
  struct node
  {
    node *next = nullptr;
    Item 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 to the end of the list\.

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

### single\_linked\_list\_const\_iterator and single\_linked\_list\_iterator 

Let's add two more classes — _single\_linked\_list\_const\_iterator_ and _single\_linked\_list\_iterator_\. These are iterators for our singly 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 _single\_linked\_list\_iterator_ type allows you to modify the element it points to, but _single\_linked\_list\_const\_iterator_ does not:

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

The _single\_linked\_list\_const\_iterator_ type contains comparison, increment, and dereference operators that are standard for an iterator\. To modify an element, let's overload a dereference operator in _single\_linked\_list\_iterator_\. The operator returns a non\-constant reference to the element\. We will also overload increment operators so that they return iterators to a non\-constant element\.

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

Let's declare _const\_iterator _and _iterator_ aliases:

```cpp
  using iterator       = single_linked_list_iterator;
  using const_iterator = single_linked_list_const_iterator;
```

## Member Functions

### Constructors

Empty list constructor:

```cpp
  single_linked_list() = default;
```

You can use _std::initializer\_list_ constructor to create a list\. To implement the constructor, let's create an empty list and sequentially insert elements to its end:

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

We will explore inserting elements at the end of _push\_back _below\.

### Destructor

Let's implement the _clear_ function, which deletes all the nodes of the list\. The list destructor simply calls the _clear_ function\.

```cpp
  ~single_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\_after_\. 

The _push\_front_ function takes one argument \(a 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)
    {
      newnode->next = m_head;
      m_head = newnode;
    }
    else 
    {
      m_head = m_tail = newnode;
    }
  }
```

The _push\_back_ function takes one argument \(a 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;
      m_tail = newnode;
    }
    else
    {
      m_head = m_tail = newnode;
    }
  }
```

Note the _if \(m\_tail\)_ check\. If we try to call a function in an empty list without this check, a [segmentation fault](https://pvs-studio.com/en/blog/terms/0063/) will occur\. However, a non\-empty list have 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 pointer\.

If the list is empty, 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\_after_ function takes two arguments: the _place_ iterator for the already existing node of the list and a new _item_ element\. The function also inserts _item_ after the _place_ node\. If we pass an invalid iterator \(null pointer\) to the method as _place_, then the new node will be inserted at the beginning of the list:

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

### 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()
{
  single_linked_list<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 the element, we traverse the list and compare the data of the current node 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 single_linked_list &>(*this).find(item);
    return { 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\. If an invalid pointer \(null pointer\) is passed to the method, the first node of the list will be deleted\.

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

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

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's possible to dereference the _ptr_ null pointer\. Here is what happens if the _ptr_ null pointer is passed to the _insert\_after_ 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 will continue\. 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 the [code fragment](https://godbolt.org/z/TsncdzTPf):

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

166 is the number of the line where dereference is possible\. Let's take a look at this line:

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

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 how to implement a singly 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 doubly linked list in C\+\+](https://pvs-studio.com/en/blog/terms/6683/)
* [Implementation of a singly linked list in C](https://pvs-studio.com/en/blog/terms/6680/)