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 singly linked list in C++. The full code is here.
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.
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 &;
// ....A singly linked list consists of nodes. Each node contains data and a pointer to the next node:
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.
private:
node *m_head = nullptr;
node *m_tail = nullptr;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 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:
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:
using iterator = single_linked_list_iterator;
using const_iterator = single_linked_list_const_iterator;Empty list constructor:
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:
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.
Let's implement the clear function, which deletes all the nodes of the list. The list destructor simply calls the clear function.
~single_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_after.
The push_front function takes one argument (a 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)
{
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:
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 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:
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;
}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()
{
single_linked_list<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 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:
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()) };
}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.
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);
}
}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_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 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:
<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:
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.
In this article, we have discussed how to implement a singly 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