Our website uses cookies to enhance your browsing experience.
Your message has been sent. We will email you at
If you do not see the email in your inbox, please check if it is filtered to one of the following folders:
Webinar: Evaluation - 05.12
A list 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.
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.
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 &;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:
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:
private:
node *m_head = nullptr;
node *m_tail = nullptr;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 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:
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:
using iterator = double_linked_list_iterator;
using const_iterator = double_linked_list_iterator;Empty list constructor:
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:
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.
We use the clear function to remove all the nodes of the list. The list destructor simply calls the clear function:
~double_linked_list()
{
clear();
}
void clear() noexcept
{
while (m_head)
{
delete std::exchange(m_head, m_head->next);
}
m_tail = nullptr;
}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:
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:
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 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.
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.
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:
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:
void foo()
{
DoubleLinkedList<int> l {1, 2, 3};
for (auto item : l)
{
// do smth
}
}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:
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()) };
}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:
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.
We researched Stack Overflow for the most common errors users face with when trying to implement lists. Let's look at some typical errors.
It's easy to make mistakes when working with lists and pointers. For example, we can accidentally dereference a null pointer:
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 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:
<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:
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.
In this article, we have discussed the implementation of a doubly linked list in C++. With Compiler Explorer and 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.
0
0
0
0