Bare bones SinglyLinkedList in C++11

Question

I have done a bare bones implementation of a singly linked list in C++, which works:

Node class

template <typename T>
class ListNode{
 template <typename U > friend class SinglyLinkedList;
private:
 T data_;
 ListNode<T>* next_;
public:
 ListNode(void):
 data_{0},
 next_{nullptr}{}
 ListNode(T data_):
 data_{data_},
 next_{nullptr} {}
};

List class:

template <typename T>
class SinglyLinkedList{
private:
 ListNode<T>* head_;
 std::size_t size_;
public:
 SinglyLinkedList():
 head_{nullptr},
 size_{0}{}
 void insert(T item){
 ListNode<T> * p{new ListNode<T>(item)};
 if (size_ == 0){
 head_ = p;
 }else{
 p->next_ = head_;
 head_ = p;
 }
 size_++;
 }
 std::size_t getSize(){
 return size_;
 }
};

Here's what I'm looking to learn and understand:

1. Where is the newed up Node in the insert deleted (released)?
2. Is there a way to implement this without new at all?

3. Is there a difference between the following lines?

   ListNode(void): data_{0}, next_{nullptr}{}
   

   and

   ListNode(void): data_(0), next_(nullptr){}
   

Answer 1

1. It seems to me that the ListNode type is part of the SinglyLinkedList. So there's no reason for that to be visible outside the SLL. I suggest making it a nested/private/hidden/secret class. (There are many ways to hide it, pick the one you like.)

2. Your method names are confusing. The std namespace has any number of collections defined. Pick one of them, and model your naming on that. For example: std::vector has a size method that returns the size. It also defines push_back and pop_back. Alternatively, std::list also defines push_front and pop_front. You need to pick a usage model for your SLL, and then choose method names compatible with it.

3. What, no iterators?

Answer 2

No observers

Although we can store data, we cannot retrieve it, delete it, nor manipulate it. As mentioned, iterators would be very helpful in this case.

Convoluted relationships

One can have something like this:

template <typename T>
class forward_list
{
 class node
 {
 node* next;
 T data;
 };
 /*the rest of the class*/
};

That way, people won't even know about existence of node, plus it cuts some words because it's place inside of list makes it clear that it is forward_list's node.

Propagating unnecessary copies

void insert(T item){
 ListNode<T> * p{new ListNode<T>(item)};
 if (size_ == 0){
 head_ = p;
 }else{
 p->next_ = head_;
 head_ = p;
 }
 size_++;
}
ListNode(T data_):
 data_{data_},
 next_{nullptr} {}

insert takes by value, which means that it will copy into node. It would be better to use move construction at least when passing the value into node:

ListNode<T> * p{new ListNode<T>(std::move(item))};
ListNode(T data_):
 data_{std::move(data_)},
 next_{nullptr} {}

This will be 3 moves in the best case, or 1 copy and 2 moves if user uses the function correctly, and 3 copies if T doesn't have move constructor.

{} for builtins mean 0

This line:

data_{0},

has one problem and one possible improvement in the good case.

1. Not all types are constructible from 0.

2. 0 is redundant for builtins

So, one of the improvements would be to remove 0, but I would ditch it altogether.

Answers to your questions

1. No. As mentioned, your code leaks memory. Bad.

2. I don't think you wanted to ask this question. I believe you wanted to ask "Can this be implemented without free store (heap) allocations?". The answer is yes, given some platform-specific tricks. It is just memory manipulation, after all. Without pointers? Probably no, probably.

3. Semantically, no. But I always use {} if the class doesn't have std::initializer_list constructor. If it has, I check documentation, and then use it if it is safe.

---

Alternative approach

I'm not sure why the idea came to me when looking at this specific post, but I believe there is a new approach to implement this without much of hassle.

Building block

struct node
{
 node* next;
 std::optional<T> data;
};

Nothing really interesting.

Constructor

forward_list():
 first{new node{}},
 last{first}
{}

The idea here is that last will always point to preallocated node. Data will not be initialized yet, so this will dodge the requirement on T for being default constructible.

push_back

Now the function gets much more simplified

// vv more about iterator later
iterator push_back(const T& elem)
{
 try
 {
 last->data = elem;
 return save_extend_end();
 }
 catch (...)
 {
 last->data.reset();
 throw;
 }
}
//almost the same for T&&
private:
iterator save_extend_end()
{
 last->next = new node{};
 iterator current{last};
 last = last->next;
 ++sz;
 return current;
}

No control flow branching now, much harder to forget. Also it provides strong exception guarantee, e.g. if something throws during the insertion, the container will get back to the state before the start of insertion.

Iterator

Writing an iterator is straightforward:

class iterator
{
 friend forward_list;
 node* current;
public:
 using iterator_category = std::forward_iterator_tag;
 using difference_type = std::size_t;
 using value_type = T;
 using reference = value_type&;
 using pointer = value_type *;
 iterator()
 {}
 iterator& operator++()
 {
 current = current->next;
 return *this;
 }
 iterator operator++(int)
 {
 auto old = *this;
 ++(*this);
 return old;
 }
 reference operator*()
 {
 return current->data.value();
 }
 friend bool operator==(iterator lhs, iterator rhs)
 {
 return lhs.current == rhs.current;
 }
 friend bool operator!=(iterator lhs, iterator rhs)
 {
 return !(lhs == rhs);
 }
private:
 iterator(node* curr):
 current{curr}
 {}
};

The using statements are there because std::iterator is deprecated now, so people need to write them themselves.

Destructor

Even destructor can now use iterators:

~forward_list()
{
 auto first = begin();
 auto last = end();
 while (first != last)
 {
 auto next = std::next(first);
 delete first.current;
 first = next;
 }
}

Demonstration

What can we do with it?

#include <algorithm>
#include <iostream>
#include <sstream>
int main()
{
 forward_list<int> list;
 std::istringstream iss{"1 2 3 4 5"};
 std::copy(std::istream_iterator<int>{iss},
 {},
 std::back_inserter(list));
 std::copy(list.begin(), list.end(), std::ostream_iterator<int>{std::cout, " "});
 std::cout << '\n';
 std::cout << "shift to the left 2 elements\n";
 std::rotate(list.begin(), std::next(list.begin(), 2), list.end());
 std::copy(list.begin(), list.end(), std::ostream_iterator<int>{std::cout, " "});
 std::cout << '\n';
}

Demo

---

Conclusion

When trying to implement something, it is better to compose it from something already existing.

Answer 3

To answer your questions:

1. Currently, nowhere (and never). You're leaking memory. Add a destructor that invokes delete on all nodes you have.
2. Not really. You could implement a stack-based version with limited size, but that's not very useful in a lot of cases. (Also, you could use malloc or any other memory allocation routine instead of new but that's not really different as you're still allocating free store memory).
3. Yes, there is (in some cases). The first line is only valid starting from C++11 and performs list initialization while the second line performs direct initialization or value initialization.