Single-linked-list in C++ with iterators

Question

I'm implementing a single linked list as close as it could be to std::forward_list. I would welcome a review and also more suggestions on what to test additionally.

#ifndef LINKED_LIST_HPP
#define LINKED_LIST_HPP
#include <iostream>
template <typename T>
class LinkedList {
private:
 struct Node {
 Node* next;
 T data;
 Node(T data): data(data), next(nullptr){
 }
};
public:
 struct iterator {
 // this should probably be const or sth 
 Node* iterNode;
 // Default constructor 
 iterator(): iterNode(nullptr)
 {
 }
 // Constructor from a node
 iterator(Node* n) : iterNode(n)
 {
 }
 // Dereferences and gets the value of the node
 const T& operator*() const
 {
 return iterNode->data;
 }
 // Prefix Increment points to the next element in the LinkedList
 iterator* operator++()
 {
 iterNode = iterNode->next;
 return this;
 }
 // Compares the two nodes of each iterator
 bool operator !=(const iterator& other) const
 {
 return iterNode!= other.iterNode;
 }
 // Is the one nodes of the iterator equal to other iterator's node
 bool operator ==(const iterator& other) const
 {
 return iterNode== other.iterNode;
 }
 // postFix increment returns an iterator to the previous node
 // but points to the next element in the LinkedList
 iterator operator++(int)
 { 
 Node* previous = iterNode;
 iterNode = iterNode->next; 
 return iterator(previous);
 }
 /*
 iterator& operator--();
 iterator operator--(int);
 value_type& operator*() const;
 */
 };
 
 void push_back(const T& value)
 {
 Node* newNode = new Node(value);
 if (!headNode)
 {
 std::cout << "!headNode" << std::endl;
 headNode = newNode;
 }
 else
 {
 auto tmp = headNode;
 Node* prevTmp = nullptr;
 std::cout << "tmp" << std::endl;
 while (tmp)
 {
 prevTmp = tmp;
 tmp = tmp->next;
 }
 prevTmp->next = newNode;
 }
 size++;
 }
 
 void insert(iterator it, const T& value)
 {
 Node* newNode = new Node(value);
 auto tmp = it.iterNode->next;
 it.iterNode->next = newNode;
 newNode->next = tmp;
 }
 
 iterator begin()
 {
 return iterator(headNode);
 }
 
 iterator end()
 {
 return iterator(nullptr);
 }
 iterator erase(iterator it)
 {
 // if deleting the first node then if this is the only element
 // mark headNode as nullptr and delete the element else make
 // the headNode point to the next element and delete the previous one.
 if (headNode == it.iterNode)
 {
 std::cout << "headNode == it.iterNode" << std::endl;
 auto nodeToDelete = it;
 if (size == 1)
 {
 std::cout << "size == 1 " << std::endl;
 headNode = nullptr;
 }
 else
 {
 std::cout << "size != 1 " << std::endl;
 headNode = (++it)->iterNode;
 }
 std::cout << "deleting" << nodeToDelete.iterNode->data << std::endl;
 delete nodeToDelete.iterNode;
 }
 else
 {
 
 auto prev = begin();
 for (auto itr = begin(); itr!=end();itr++)
 {
 if (itr == it)
 {
 prev.iterNode->next = (++itr)->iterNode;
 delete it.iterNode;
 break;
 }
 prev = itr;
 }
 }
 }
public:
 LinkedList() : size(0), headNode(nullptr){
 }
 
 ~LinkedList()
 {
 Node* current = headNode;
 while (current)
 {
 Node* next = current->next;
 delete current;
 current = next;
 }
 }
private:
 int size;
 Node* headNode;
};
#endif //LINKED_LIST_HPP

This is testing using the g++ framework

#include "linkedlist.hpp"
#include <gtest/gtest.h>
TEST(LinkedListTest, PushBackTest) 
{
 LinkedList<int> myList;
 LinkedList<int>::iterator it;
 for (int i=1; i<=5; ++i) myList.push_back(i);
 
 it = myList.begin();
 ASSERT_EQ(*it, 1);
 
 auto counter = 1;
 for (auto itr = myList.begin(); itr!=myList.end();++itr)
 {
 ASSERT_EQ(*itr, counter);
 counter++;
 }
}
TEST(LinkedListTest, EraseTest) 
{
 LinkedList<int> myList;
 LinkedList<int>::iterator it;
 myList.push_back(1);
 it = myList.begin();
 // Deleting when is the only node and on the first place
 myList.erase(it);
 for (int i=2; i<=5; ++i) myList.push_back(i);
 
 it = myList.begin();
 auto counter = 2;
 // Ensure values are as expected
 for (auto itr = myList.begin(); itr!=myList.end();++itr)
 {
 ASSERT_EQ(*itr, counter);
 counter++;
 }
 
 // Deleting when is not the only node but is on the first place
 it = myList.begin();
 std::cout << "Failing case" << std::endl;
 myList.erase(it);
 counter = 3;
 // Ensure values are as expected
 for (auto itr = myList.begin(); itr!=myList.end();++itr)
 {
 ASSERT_EQ(*itr, counter);
 counter++;
 }
 it = myList.begin();
 it++;
 // Deleting an element from the middle and ensure everything is connected correctly
 myList.erase(it);
 counter = 3;
 for (auto itr = myList.begin(); itr!=myList.end();++itr)
 {
 if (counter == 4) counter++;
 ASSERT_EQ(*itr, counter);
 counter++;
 }
 
}

Answer 1

1. Remember the rule of three. The implicitly declared copy- and move- ctor and assignment are unsuitable for LinkedList.

2. Two-space indentation doesn't really stand out. Consider doubling it.

3. If you add trace-output to your code, the least you can do is keeping it out of standard output. Error / Log stream is the proper destination. Also, design it for easy disabling and / or removal. Yes, that means using the preprocessor here.

4. Avoid std::endl. The manual flush is nearly always superfluous, just tanking performance. If you actually need it, be explicit and use std::flush.
   See "What is the C++ iostream endl fiasco? ".

5. If you use aggregate-initialization for your nodes, you need no custom ctor. Emplacing, move-constructing and copy-constructing would otherwise already be three ctors, or a templated one.

6. Don't make data-members public without good reason. friend can be used to selectively let some other code in.

7. Use in-class-initialization for all members you can. It simplifies your ctors.
   As a bonus, you can more often define them = default;, making the type trivial, which has its own benefits.

8. Comments are for describing your reasoning, the overarching design, and point out subtleties.
   Don't bore your readers to tears by having them read the same thing twice, once in code and once in comment.

   Doc-comments which are extracted to create basic documentation must stand without the code, so should be treated a bit more lenient in this regard.

9. // this should probably be const or sth No, really not. It is exactly as it should be. Or it would be, if you returned T& from operator*.

10. Currently, you are using the specific type half the time without rhyme or reason, consider leaning more on auto.

11. If a function cannot throw by design, mark it noexcept. Others can pick it up and take advantage of the guarantee.

12. Don't fear pointing at pointers.

    It can significantly simplify some code:

    template <class... Xs>
    void emplace_back(Xs&&...xs) {
     auto p = &headNode;
     while (*p)
     p = &p[0]->next;
     *p = new Node{{}, T(std::forward<Xs>(xs)...)}; // Using modified Node
     ++size;
    }
    

13. Expand the iterators, and the list-class itself. Currently, you just have the bare basics to have something move, but it is just a beginning.

14. Upgrade to C++20:

    • != will be synthesised from ==, so no need to define it.
    • Most any of your members can be made constexpr, allowing use at compile-time.

• user3638488: Don't make data-members public without good reason. friend can be used to selectively let some other code in. So you're suggesting to make the struct iterator a class and have a friend getter ? or make struct Node a class and have friend getters? Or both ?
• Deduplicator: No, I mean that you can make your list a friend. Node should be a private member of the list, containing only data-members.

Answer 2

What happens when you copy a LinkedList object? GCC warns

269711.cpp:6:7: warning: ‘class LinkedList<int>’ has pointer data members [-Weffc++]
 6 | class LinkedList {
 | ^~~~~~~~~~
269711.cpp:6:7: warning: but does not declare ‘LinkedList<int>(const LinkedList<int>&)’ [-Weffc++]
269711.cpp:6:7: warning: or ‘operator=(const LinkedList<int>&)’ [-Weffc++]
269711.cpp:165:9: note: pointer member ‘LinkedList<int>::headNode’ declared here
 165 | Node* headNode;
 | ^~~~~~~~

And I don't see any tests that involve copying.

Some other warnings worth fixing:

269711.cpp:36:15: warning: prefix ‘LinkedList<T>::iterator* LinkedList<T>::iterator::operator++()’ should return ‘LinkedList<T>::iterator&’ [-Weffc++]
 36 | iterator* operator++()
 | ^~~~~~~~

269711.cpp: In instantiation of ‘LinkedList<T>::iterator LinkedList<T>::erase(LinkedList<T>::iterator) [with T = int]’:
269711.cpp:199:15: required from here
269711.cpp:147:3: warning: no return statement in function returning non-void [-Wreturn-type]
 147 | }
 | ^

269711.cpp: In instantiation of ‘LinkedList<T>::Node::Node(T) [with T = int]’:
269711.cpp:71:21: required from ‘void LinkedList<T>::push_back(const T&) [with T = int]’
269711.cpp:179:44: required from here
269711.cpp:10:7: warning: ‘LinkedList<int>::Node::data’ will be initialized after [-Wreorder]
 10 | T data;
 | ^~~~
269711.cpp:9:11: warning: ‘LinkedList<int>::Node* LinkedList<int>::Node::next’ [-Wreorder]
 9 | Node* next;
 | ^~~~
269711.cpp:11:5: warning: when initialized here [-Wreorder]
 11 | Node(T data): data(data), next(nullptr){
 | ^~~~

I really recommend enabling more warnings when you compile.

Answer 3

You need to publish iterator traits so you can use your class with standard algorithms! Your test code did not try passing your list's iterators to std::find etc. Also ensure that you can use a LinkedList in a range-based for loop.

Don't write unnecessary or implicit type conversions.
return iterator(headNode);
does not need the explicit construction since the iterator constructor is not marked explicit. That is,
return headNode;
means the same thing.

Your destructor should just call clear and not have to do the work directly.

The guard name LINKED_LIST_HPP is not specific enough or unique. It could easily clash if this was used in a project with many libraries and nested library usage. If you must use such guards (#pragma once is supported by all the major compilers) always use a UUID or the like.

---

Keep up the good work!

• Deduplicator: Considering that .clear() is the more rarely used one, shouldn't rather .clear() be defined using the dtor?
• Deduplicator: See what zwol has to say about #pragma once.
• uli: How so, @deduplicator? The only way I could imagine is to invoke the destructor and then use in-place construction to reinstate the object.
• Deduplicator: @uli *this = LinkedList(); after defining the move-ctor. But yes, manual call to dtor +in-place-new using default-ctor would also work, as no virtual bases/functions to complicate inheritance.
• uli: Interesting, @Deduplicator, I hadn't thought of that.

Answer 4

Having Tests

Big plus! I have often wished that code I worked on would have more tests or any tests at all.

Advancing to last element

This locates the last node of the list in prevTmp (not a speaking name, btw) and is unnecessarily complicated:

auto tmp = headNode;
Node* prevTmp = nullptr;
while (tmp)
{
 prevTmp = tmp;
 tmp = tmp->next;
}

One thing is that you already established that headNode is not null (in code not shown here), so the first iteration of while (tmp) will always execute the loop body. With that in mind, try this instead:

auto tmp = headNode;
while (tmp->next) {
 tmp = tmp->next;
}

After that, you have an element where tmp->next is null, which is almost self-documenting a free place at the end of the linked list.

Rule of Five

Your linked list has implicitly defined copy-ctor and assignment operator, which it shouldn't have. Disable them or implement them properly.

push_back() Method

Why have this, which is the most inefficient way to use a singly-linked list? If you look at the STL (the origin of the C++ standard library), you won't find a push_front() method in its vector container either, exactly because it is inefficient! Same for your class, just don't implement it, but implement a push_front() and pop_front() instead!

insert() Behaviour

I believe that insertion in the STL specifies the position before (!) which you insert, so you can call container.insert(value, container.end()). Your version does it differently.

In any case, make sure to consider inserting into an empty container at positions container.begin() and container.end() in your tests!

• Deduplicator: "insert() Behaviour: I believe that insertion in the STL specifies the position before (!) which you insert" Which is why the forward_list instead implements .insert_after(). Actually, it has many changes to accommodate only having forward-iterators without sacrificing efficiency.