Generic Single Linked List Using Smart Pointers Follow up

Question

I am extending this post following from here. I made some of the changes that I could make in the previous post. Although, I have not been successful in creating iterators for my class.

The reason for the new post is to see if there is any additional changes I need to make to my code. As well as steps in creating iterators for this class. Should I perhaps follow what is done here?

I am still in the learning process with smart pointers and there is still much I need to learn, I find it useful when people post detailed answers instead of computer science jargon that my ears are still new to.

Here is my header file:

#ifndef SingleLinkedList_h
#define SingleLinkedList_h
template <class T>
class SingleLinkedList {
private:
 struct Node {
 T data;
 std::unique_ptr<Node> next = nullptr;
 // disable if noncopyable<T> for cleaner error msgs
 explicit Node(const T& x, std::unique_ptr<Node>&& p = nullptr)
 : data(x)
 , next(std::move(p)) {}
 // disable if nonmovable<T> for cleaner error msgs
 explicit Node(T&& x, std::unique_ptr<Node>&& p = nullptr)
 : data(std::move(x))
 , next(std::move(p)) {}
 };
 std::unique_ptr<Node> head = nullptr;
 Node* tail = nullptr;
 void do_pop_front() {
 head = std::move(head->next);
 }
public:
 // Constructors
 SingleLinkedList() = default; // empty constructor 
 SingleLinkedList(SingleLinkedList const &source); // copy constructor
 // Rule of 5
 SingleLinkedList(SingleLinkedList &&move) noexcept; // move constructor
 SingleLinkedList& operator=(SingleLinkedList &&move) noexcept; // move assignment operator
 ~SingleLinkedList(); 
 // Overload operators
 SingleLinkedList& operator=(SingleLinkedList const &rhs);
 // This function is for the overloaded operator << 
 void display(std::ostream &str) const {
 for (Node* loop = head.get(); loop != nullptr; loop = loop->next.get()) {
 str << loop->data << "\t";
 }
 str << "\n";
 }
 friend std::ostream& operator<<(std::ostream &str, SingleLinkedList &data) {
 data.display(str);
 return str;
 }
 // Memeber functions
 void swap(SingleLinkedList &other) noexcept;
 bool empty() const { return head.get() == nullptr; }
 int size() const;
 void push_back(const T &theData); 
 void push_back(T &&theData);
 void push_front(const T &theData);
 void insertPosition(int pos, const T &theData);
 void clear();
 void pop_front();
 void pop_back();
 void deleteSpecific(int delValue);
 bool search(const T &x);
};
template <class T>
SingleLinkedList<T>::SingleLinkedList(SingleLinkedList<T> const &source) {
 for(Node* loop = source.head.get(); loop != nullptr; loop = loop->next.get()) {
 push_back(loop->data);
 }
}
template <class T>
SingleLinkedList<T>::SingleLinkedList(SingleLinkedList<T>&& move) noexcept {
 move.swap(*this);
}
template <class T>
SingleLinkedList<T>& SingleLinkedList<T>::operator=(SingleLinkedList<T> &&move) noexcept {
 move.swap(*this);
 return *this;
}
template <class T>
SingleLinkedList<T>::~SingleLinkedList() {
 clear();
}
template <class T>
void SingleLinkedList<T>::clear() {
 while (head) {
 do_pop_front();
 }
}
template <class T>
SingleLinkedList<T>& SingleLinkedList<T>::operator=(SingleLinkedList const &rhs) {
 SingleLinkedList copy{ rhs };
 swap(copy);
 return *this;
}
template <class T>
void SingleLinkedList<T>::swap(SingleLinkedList &other) noexcept {
 using std::swap;
 swap(head, other.head);
 swap(tail, other.tail);
}
template <class T>
int SingleLinkedList<T>::size() const {
 int size = 0;
 for (auto current = head.get(); current != nullptr; current = current->next.get()) {
 size++;
 }
 return size;
}
template <class T>
void SingleLinkedList<T>::push_back(const T &theData) {
 std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);
 if (!head) {
 head = std::move(newNode);
 tail = head.get();
 }
 else {
 tail->next = std::move(newNode);
 tail = tail->next.get();
 }
}
template <class T>
void SingleLinkedList<T>::push_back(T &&thedata) {
 std::unique_ptr<Node> newnode = std::make_unique<Node>(std::move(thedata));
 if (!head) {
 head = std::move(newnode);
 tail = head.get();
 }
 else {
 tail->next = std::move(newnode);
 tail = tail->next.get();
 }
}
template <class T>
void SingleLinkedList<T>::push_front(const T &theData) {
 std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);
 newNode->next = std::move(head);
 head = std::move(newNode);
}
template <class T>
void SingleLinkedList<T>::insertPosition(int pos, const T &theData) {
 if (pos > size() || pos < 0) {
 throw std::out_of_range("The insert location is invalid.");
 }
 auto node = head.get();
 int i = 0;
 for (; node && node->next && i < pos; node = node->next.get(), i++);
 if (i != pos) {
 throw std::out_of_range("Parameter 'pos' is out of range.");
 }
 auto newNode = std::make_unique<Node>(theData);
 if (node) {
 newNode->next = std::move(node->next);
 node->next = std::move(newNode);
 }
 else {
 head = std::move(newNode);
 }
}
template <class T>
void SingleLinkedList<T>::pop_front() {
 if (empty()) {
 throw std::out_of_range("List is Empty!!! Deletion is not possible.");
 }
 do_pop_front();
}
template <class T>
void SingleLinkedList<T>::pop_back() {
 if (!head.get()) {
 throw std::out_of_range("List is Empty!!! Deletion is not possible.");
 }
 auto current = head.get();
 Node* previous = nullptr;
 while (current->next != nullptr) {
 previous = current;
 current = current->next.get();
 }
 tail = previous;
 previous->next = nullptr;
}
template <class T>
void SingleLinkedList<T>::deleteSpecific(int delValue) {
 if (!head.get()) {
 throw std::out_of_range("List is Empty!!! Deletion is not possible.");
 }
 auto temp1 = head.get();
 Node* temp2 = nullptr;
 while (temp1->data != delValue) {
 if (temp1->next == nullptr) {
 throw std::invalid_argument("Given node not found in the list!!!");
 }
 temp2 = temp1;
 temp1 = temp1->next.get();
 }
 temp2->next = std::move(temp1->next);
}
template <class T>
bool SingleLinkedList<T>::search(const T &x) {
 auto current = head.get();
 while (current) {
 if (current->data == x) {
 return true;
 }
 current = current->next.get();
 }
 return false;
}
#endif /* SingleLinkedList_h*/

Here is the main.cpp file:

//
// main.cpp
// Data Structure - LinkedList
//
// Created by Morgan Weiss on 7/24/2018
// Copyright © 2018 Morgan Weiss. All rights reserved.
//
#include <algorithm>
#include <cassert>
#include <iostream>
#include <memory>
#include <utility>
#include <stdexcept>
#include <ostream>
#include <iosfwd>
#include <stdexcept>
#include "SingleLinkedList.h"
int main(int argc, const char * argv[]) {
 ///////////////////////////////////////////////////////////////////////
 ///////////////////////////// Single Linked List //////////////////////
 ///////////////////////////////////////////////////////////////////////
 SingleLinkedList<int> obj;
 obj.push_back(2);
 obj.push_back(4);
 obj.push_back(6);
 obj.push_back(8);
 obj.push_back(10);
 std::cout<<"\n--------------------------------------------------\n";
 std::cout<<"---------------displaying all nodes---------------";
 std::cout<<"\n--------------------------------------------------\n";
 std::cout << obj << "\n";
 std::cout<<"\n--------------------------------------------------\n";
 std::cout<<"----------------Inserting At Start----------------";
 std::cout<<"\n--------------------------------------------------\n";
 obj.push_front(50);
 std::cout << obj << "\n";
 std::cout<<"\n--------------------------------------------------\n";
 std::cout<<"-------------inserting at particular--------------";
 std::cout<<"\n--------------------------------------------------\n";
 obj.insertPosition(5,60);
 std::cout << obj << "\n";
 std::cout << "\n--------------------------------------------------\n";
 std::cout << "-------------Get current size ---=--------------------";
 std::cout << "\n--------------------------------------------------\n";
 std::cout << obj.size() << "\n";
 std::cout<<"\n--------------------------------------------------\n";
 std::cout<<"----------------deleting at start-----------------";
 std::cout<<"\n--------------------------------------------------\n";
 obj.pop_front();
 std::cout << obj << "\n";
 std::cout<<"\n--------------------------------------------------\n";
 std::cout<<"----------------deleting at end-----------------------";
 std::cout<<"\n--------------------------------------------------\n";
 obj.pop_back();
 std::cout << obj << "\n";
 std::cout<<"\n--------------------------------------------------\n";
 std::cout<<"--------------Deleting At Particular--------------";
 std::cout<<"\n--------------------------------------------------\n";
 obj.deleteSpecific(4);
 std::cout << obj << "\n";
 obj.search(8) ? printf("yes"):printf("no");
 std::cout << "\n--------------------------------------------------\n";
 std::cout << "--------------Testing copy----------------------------";
 std::cout << "\n--------------------------------------------------\n";
 SingleLinkedList<int> obj1 = obj;
 std::cout << obj1 << "\n";
 //std::cout << "\n-------------------------------------------------------------------------\n";
 //std::cout << "--------------Testing to insert in an empty list----------------------------";
 //std::cout << "\n-------------------------------------------------------------------------\n";
 //SingleLinkedList<int> obj2;
 //obj2.insertPosition(5, 60);
 //std::cout << obj2 << "\n";
 std::cin.get();
}

• Snorrlaxxx: @hoffmale Thank you, I really appreciate that.
• Snorrlaxxx: @hoffmale Are you still planning to do a review? I think I got it down now through the help of the answers below as well as Toby hooking me up with how to create an iterator class. I may just move onto the double linked list revision and apply what I did here. That way if I still messed something up then I will know where to make the appropriate revisions in the single linked list, i.e. killing two birds with one stone.
• Snorrlaxxx: @hoffmale To be honest, I do not have a reason. Just so I understand, are you saying for tail deletion for a single linked list can be done in O(1)?

Answer 1

Move public section of the class to the top

I prefer, and suggest others, to put the public section of a class before the protected and private sections.

The rationale for it is that users of the class want to see the public section of the class. It is less important to them to see what's in the protected and private sections. It does not make sense that they will have to wade through less important sections of the class before they get to the most important section.

template <class T>
class SingleLinkedList {
 public:
 // Constructors
 SingleLinkedList() = default; // empty constructor 
 ...
 protected:
 private:
 struct Node {
 ...
 };
 ...
}; 

Remove display(std::ostream &str)

I understand that you need the function at the moment to display the contents of an object. However, it's too tightly coupled with the class. Different users may want to display an object of the class differently. You can't support that easily if display is the only function the user has access to.

This should be motivation for you to implement the iterator class. When you have the iterator class ready, the operator<<(std::ostream&, SingleLinkedList const&) function can be moved out of the class and the friend-ship won't be necessary. The current functionality can be moved to a non-member function.

Also note that the list object should be a const&.

template <typename T>
std::ostream& operator<<(std::ostream &str, SingleLinkedList<T> const& list)
{
 // This will work as soon as you have begin() and end() member functions
 for ( auto const& item : list )
 { 
 str << item << "\t";
 }
 return str;
}

insertPosition needs a better name

You are not inserting a position. You are inserting an item at a position. For that reason, I think insert_at_position is more appropriate and follows the naming convention of other functions.

If insert_at_position is too verbose, the simpler name, insert will be better than insertPosition, IMO.

deleteSpecific needs a better name

I think the simpler name remove() will be better.

If you decide to keep deleteSpecific, I would suggest changing it to delete_specific to keep the function names consistent.

• hoffmale: I agree with most of the points, but the first section is about a personal preference, and personal preferences are just that: Personal. Different people have different preferences for different reasons (e.g. I like to have my data members at or near the top so I can easily grasp the memory layout and possible access patterns, which is important for high performance). This is just the two of us, and we already have conflicting points of view on the subject matter (toss in OP for a third one), so I doubt this makes a good generalization.
• R Sahu: @hoffmale, you make a valid point. I think both have merits. We can let the OP choose what makes sense to them.
• Snorrlaxxx: I implemented the iterator that Toby Speight suggested in the post codereview.stackexchange.com/questions/200861/…
• Snorrlaxxx: Although, when I delete the display function and use the code for the code you gave me to use I get this error: error C2662: 'SingleLinkedList<int>::iterator SingleLinkedList<int>::begin(void)': cannot convert 'this' pointer from 'const SingleLinkedList<int>' to 'SingleLinkedList<int> &'
• Snorrlaxxx: removing the const did the trick though :)

Answer 2

• push_front does not update tail. Usually no problem, unless applied to an empty list (tail remains nullptr, which push_back doesn't check, etc).

• Ditto for insertPosition.

• Ditto for pop_back. Popping the last element from the list shall update head.

• push_front(const T &&theData) is missing.

• insertPosition looks too cautious. You immediately know that pos <= size(); there is no point to not trust yourself. i != pos is impossible.

  As a side note, the interface doesn't look clear. I'd expect insertPosition(0, ...) be _always_ equivalent topush_front`.

• size() shall return size_t. In any case, there is no reason to return a signed value. Similarly, the position arguments shall be size_t, or at least unsigned.

• Snorrlaxxx: For the first point just so I understand, this should fix the problem: template '<class T> void SingleLinkedList<T>::push_front(const T &theData) { if (empty()) { throw std::out_of_range("List is empty") } std::unique_ptr<Node> newNode = std::make_unique<Node>(theData); newNode->next = std::move(head); head = std::move(newNode); }'
• Snorrlaxxx: Sorry I do not know how to make inserting code on comments nice :(
• hoffmale: That should be push_front(T&&) (no const T&&).

Answer 3

Just small addition to great answers.

Commenting obvious stuff

I would delete all comments, really. You can safely assume that people who read you code will know what constructor etc is. Such commenting is really distracting.

// Constructors
 SingleLinkedList() = default; // empty constructor 
 SingleLinkedList(SingleLinkedList const &source); // copy constructor

Small inconsistency

In one case you are using auto (correct)

for (auto current = head.get(); current != nullptr; current = current->next.get()) {
 size++;
}

In other case you don't.

for (Node* loop = head.get(); loop != nullptr; loop = loop->next.get()) {
 str << loop->data << "\t";
}

It is really important (especially in big projects with millions LOC) to keep things as much consistent as you can.

Answer 4

Optimization

Getting the best performance for any operation is the Holy Grail for any programmer - but is this always required?

There's this famous quote by Donald Knuth:

Premature optimization is the root of all evil.

While this is sometimes taken out of context, he basically wanted to express that you shouldn't worry about small inefficiencies in the code, unless you know that extra performance is needed (e.g. by profiling performance afterwards, or by design requirements beforehand). The extra complexity added by those optimizations usually makes debugging and maintaining the code much harder.

And this can be observed in the implementation: There is an optimization to allow for \$\mathcal{O}(1)\$ tail insertion by storing a tail pointer. As other answers have pointed out, that tail pointer isn't updated correctly in all places.

After getting OP's reasoning for the optimization (i.e. none), it seems like this one had been done prematurely.

Know thy data structures

Note: In the following, I'm assuming a forward singly linked list (head and next pointers). Similar arguments apply for reverse singly linked lists (tail and prev pointers).

Operations on a singly linked lists tail are usually one of its worst case ones, as finding the tail requires a full traversal of the list.

If it is known beforehand that operations on the tail will be critical, you'd normally not consider a singly linked list (other than maybe the reverse one), as other data structures like a doubly linked list or even a dynamically growing array (std::vector) inherently provide better performance characteristics for that use case.

The only special case I can think of where this might be useful is that the program

• runs on a platform with heavy memory constraints

• and has lots of tail insertions, but few to none tail deletions,

like a queue for an embedded device (where the extra memory overhead of a doubly linked list is too much) - but even then I'd still want to know why this is better than a circular buffer (which has even less memory overhead, as it needs no next pointers).

Design

Currently, the SingleLinkedList allows for move- and copy-constructable types, but doesn't provide any support for types that aren't (like std::mutex). If SingleLinkedList should also support those types (which require in-place construction), I'd suggest adding emplace, emplace_front and emplace_back member functions (corresponding to insert, push_front and push_back respectively).

Note that this will require an additional Node constructor:

template<typename... Args, typename = std::enable_if_t<std::is_constructible_v<T, Args&&...>>>
Node(std::unique_ptr<Node>&& next, Args&&... args) noexcept(std::is_nothrow_constructible_v<T, Args&&...>)
 : data{std::forward<Args>(args)...}, next{std::move(next)} {}

Some necessary changes:

• next cannot be at the end of the parameter list (explanation)

• next cannot have a default value (since it isn't at the end of the parameter list), nor can the constructor be overloaded regarding the presence of next (it either has to always be there or always be absent, anything else would result in ambiguities). I chose "It has to be there", YMMV.

  (Technically not the whole truth, as you could e.g. use tag types to choose the correct overload. This was meant as a simple example.)

• This requires the <type_traits> header for, well, type traits.

  The type traits help constricting the constructor to only accept arguments that are valid for T, so instantiation fails as early as possible (the std::make_unique<Node>(...) call). As a bonus, the constructor is automatically gets the same exception specification as the internally called T constructor.

This constructor can replace the existing ones in cases where next != nullptr. For consistency, I'd suggest dropping the next parameter from those constructors so there is only one order of parameters to pass a next node (having both (value, node) and (node, value) work can be confusing).

An implementation of emplace_front can be as simple as this:

template <class T>
template <typename... Args>
void SingleLinkedList<T>::emplace_front(Args&&... args) {
 head = std::make_unique<Node>(std::move(head), std::forward<Args>(args)...);
 if(!tail) tail = head.get(); // update tail if list was empty before
}

This has been carefully crafted to have the same strong exception guarantee as the original push_front:

• If the allocation fails in std::make_unique, the head isn't changed (because it is passed as std::unique_ptr<Node>&&).

• Inside the Node, data gets constructed first. If that throws, next (in this case head) will not be moved from yet, i.e. it's still valid.

It's subtleties like these that makes writing code with a strong exception guarantee hard to get right. You can simply adapt the original push_front implementation if that makes you more comfortable, as it's more robust regarding other changes (e.g. changing the constructors next parameter's type to std::unique_ptr<Node>, or reordering Node::data after Node::next).

Of course, push_front can now be reimplemented in terms of emplace_front:

template <class T>
void SingleLinkedList<T>::push_front(const T &theData) {
 emplace_front(theData);
}
template <class T>
void SingleLinkedList<T>::push_front(T&& theData) {
 emplace_front(std::move(theData));
}

• hoffmale: If something is unclear (especially regarding some of the subtleties I mentioned), feel free to ask!
• Snorrlaxxx: Hi hoffmale, fist off. I really appreciate your continued support and advising me. You are excellent with explaining these difficult concepts (difficult for me) in simple lay language. I would like to know where in my code I did not update tail properly so I can fix that. In regards to the the Design part of your answer. I will gladly add emplace, emplace_back, and emplace_front. But I must admit the node constructor you defined there seems pretty daunting to me and there are things you have like enable_if_t that I am seeing for the first time. Also, the additional changes you mention after...
• Snorrlaxxx: I do not fully understand what to change. For example "next cannot be at the end of the parameter list". I am not sure where I did that in my code or what I need to change. I am now going to start working on double linked list, should I also include emplace, emplace_front, emplace_back as well?
• hoffmale: @Snorrlaxxx: 1) See vnp's answer (push_front among others). I didn't fix that in my example code. 2) std::enable_if_t basically evaluates either to a type (void by default) if the condition is true, and otherwise doesn't evaluate to anything. This can be used to enable or disable function under certain circumstances (like the constructor will be disabled if T isn't constructible usingArgs). 3) Maybe I should clarify this, but that part is basically only explanations for what I did and why I did it that way.
• Snorrlaxxx: I just took a look at vnp's answer but I showed him what I did as a solution to his first point, but I was not sure if I was correct or not.