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.

#ifndef SingleLinkedList_h

template <class T>
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)) {}
};
Node* tail = nullptr;

void do_pop_front() {
}

public:
// Constructors
SingleLinkedList() = default;                                           // empty constructor

// Rule of 5

// 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
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>
for(Node* loop = source.head.get(); loop != nullptr; loop = loop->next.get()) {
push_back(loop->data);
}
}

template <class T>
move.swap(*this);
}

template <class T>
move.swap(*this);
return *this;
}

template <class T>
clear();
}

template <class T>
do_pop_front();
}
}

template <class T>
swap(copy);
return *this;
}

template <class T>
using std::swap;
swap(tail, other.tail);
}

template <class T>
int size = 0;
for (auto current = head.get(); current != nullptr; current = current->next.get()) {
size++;
}
return size;
}

template <class T>
std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);

}

else {
tail->next = std::move(newNode);
tail = tail->next.get();
}
}

template <class T>
std::unique_ptr<Node> newnode = std::make_unique<Node>(std::move(thedata));

}

else {
tail->next = std::move(newnode);
tail = tail->next.get();
}
}

template <class T>
std::unique_ptr<Node> newNode = std::make_unique<Node>(theData);
}

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.");
}
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 {
}
}

template <class T>
if (empty()) {
throw std::out_of_range("List is Empty!!! Deletion is not possible.");
}

do_pop_front();
}

template <class T>
throw std::out_of_range("List is Empty!!! Deletion is not possible.");
}

Node* previous = nullptr;

while (current->next != nullptr) {
previous = current;
current = current->next.get();
}
tail = previous;
previous->next = nullptr;
}

template <class T>

throw std::out_of_range("List is Empty!!! Deletion is not possible.");
}

Node* temp2 = nullptr;
while (temp1->data != delValue) {
if (temp1->next == nullptr) {
}
temp2 = temp1;
temp1 = temp1->next.get();
}
temp2->next = std::move(temp1->next);
}

template <class T>
while (current) {
if (current->data == x) {
return true;
}
current = current->next.get();
}
return false;
}



Here is the main.cpp file:

//
//  main.cpp
//
//  Created by Morgan Weiss on 7/24/2018
//

#include <algorithm>
#include <cassert>
#include <iostream>
#include <memory>
#include <utility>
#include <stdexcept>
#include <ostream>
#include <iosfwd>
#include <stdexcept>

int main(int argc, const char * argv[]) {

///////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////
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";
std::cout << obj1 << "\n";

//std::cout << "\n-------------------------------------------------------------------------\n";
//std::cout << "--------------Testing to insert in an empty list----------------------------";
//std::cout << "\n-------------------------------------------------------------------------\n";
//obj2.insertPosition(5, 60);
//std::cout << obj2 << "\n";

std::cin.get();
}

• @hoffmale Thank you, I really appreciate that. – Snorrlaxxx Aug 6 '18 at 0:33
• @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 Aug 7 '18 at 0:50
• @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)? – Snorrlaxxx Aug 8 '18 at 0:14

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>

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.

• 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. – hoffmale Aug 6 '18 at 11:06
• @hoffmale, you make a valid point. I think both have merits. We can let the OP choose what makes sense to them. – R Sahu Aug 6 '18 at 14:38
• I implemented the iterator that Toby Speight suggested in the post codereview.stackexchange.com/questions/200861/… – Snorrlaxxx Aug 7 '18 at 0:40
• 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 Aug 7 '18 at 0:41
• removing the const did the trick though :) – Snorrlaxxx Aug 7 '18 at 0:42
• 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.

• 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 Aug 7 '18 at 0:28
• Sorry I do not know how to make inserting code on comments nice :( – Snorrlaxxx Aug 7 '18 at 0:29
• That should be push_front(T&&) (no const T&&). – hoffmale Aug 8 '18 at 23:31

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


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.

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>
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>

• @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. – hoffmale Aug 8 '18 at 23:27