C++ Linked list with smart pointers

Question

This seems to work fine, but I'm very new to C++ and would like any suggestions for improvements. Areas I have the most trouble with are:

• Namespacing (honestly, it's still half looking stuff up and making an educated guess with typename blah blah blah). Is there a "cleaner" way to implement this?

• Various C++ idioms (copy and swap) that aren't as common in, say, C or Java. There are good answers relating to copy and swap in particular, but I just don't quite "get it" yet. The principal makes sense, but specifically what to do with regards to protecting against exceptions in the copy constructor itself

• Adding to that, exceptions in general in C++ (coming from the strict Java approach and the "check errno/return value/whatever" C approach), although in the context of this code it's more about guaranteeing exception safety where people would expect it (see above).

• General good "style". Specifically, what's the cleanest way to implement the Node class in data structures where we see something like this? this plays into how namespacing can get tricky. There seems to be a tradeoff of encapsulation (e.g. defining a struct node within the LinkedList class seems intuitively more "reasonable", but this makes dealing with nodes in any function that may be written outside my definition file strewn with typename).

  • Another example: should root really be a unique_ptr here instead of a regular object? It certainly made my code easier to write, but I'm curious as to arguments for or against it.

• I'm still fairly unclear as to when exactly I need the template declaration for classes (see the copy constructor for instance, where it takes LinkedList as an argument instead of LinkedList<T>, but it worked, which seems odd).

I understand the use case between e.g. unique_ptr and shared_ptr for the most part, but certainly want to know if I'm misusing anything here. There is nothing fancy (like a reference to the tail to make insertion faster), but I just want to make sure I'm starting out on the right foot as the more I use C++ it seems the less I actually understand anything.

LinkedList class header

#ifndef _NEW_LL_H
#define _NEW_LL_H
#include<memory>
#include "node.h"
template <typename T>
class LinkedList {
 public:
 LinkedList() {};
 ~LinkedList() {}; // destructor
 LinkedList(LinkedList const & ll); // copy constructor
 LinkedList& operator=(LinkedList const & ll); // copy assignment
 LinkedList(LinkedList && ll); // move constructor
 LinkedList& operator=(LinkedList && ll); // move assignment
 void append(T const& item);
 // deletes the first node containing item, returns true if successful
 bool delete_node(T const& item);
 void print();
 bool search(T const& item);
 std::unique_ptr<typename Node<T>::Node> root;
 // std::unique_ptr<Node> tail; maybe later
};
#endif

Node header

#ifndef _NODE_H
#define _NODE_H
#include<memory>
template <typename T>
class Node {
public:
 T item;
 std::unique_ptr<Node> next=nullptr;
 Node(T const& t); // default constructor
 Node(Node const& insert); // copy constructor
};
#endif

Implementation file

#include <iostream>
#include <memory>
#include "new_ll.h"
using namespace std;
template <typename T>
LinkedList<T>::LinkedList(LinkedList const & ll) {
 if(ll.root) root = make_unique<Node<T>>(*ll.root);
} // copy constructor calls node's recursively
template <typename T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList<T> const & ll) {
 if(ll.root) root = make_unique<Node>(*ll.root);
} // copy assignment
template <typename T>
LinkedList<T>::LinkedList(LinkedList<T> && ll) {
 root = move(ll.root);
} // move constructor
template <typename T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList<T> && ll) {
 root = move(ll.root);
} // move assignment
template <typename T>
void LinkedList<T>::append(T const& item) {
 if(root==nullptr) {
 root = make_unique<Node<T>>(item);
 return;
 }
 Node<T> *tmpNode = root.get();
 while(tmpNode->next!=nullptr) tmpNode=tmpNode->next.get();
 tmpNode->next = make_unique<Node<T>>(item);
}
template <typename T>
bool LinkedList<T>::delete_node(T const& item) {
 if(root->item == item) {
 root = move(root->next);
 return true;
 }
 Node<T> *tmpNode = root.get();
 while(tmpNode->next!=nullptr) {
 if(tmpNode->next->item == item) {
 tmpNode->next = move(tmpNode->next->next);
 return true;
 }
 tmpNode = tmpNode->next.get();
 }
 return false;
}
template <typename T>
void LinkedList<T>::print() {
 Node<T> *tmpNode = root.get();
 while(tmpNode!=nullptr) {
 cout << "Address: " << tmpNode << " value: " << tmpNode->item << endl;
 tmpNode = tmpNode->next.get();
 }
}
template <typename T>
bool LinkedList<T>::search(T const& item) {
 Node<T> *tmpNode = root.get();
 while(tmpNode!=nullptr) {
 if(tmpNode->item == item) return true;
 tmpNode = tmpNode->next.get();
 }
 return false;
}
template <typename T>
Node<T>::Node(T const& t) : item(t) {}; // default constructor
template <typename T>
Node<T>::Node(Node const& insert) : item(insert.item) {
 if(insert.next) next = make_unique<Node<T>>(*insert.next);
}; // copy constructor

Any input is appreciated! I just feel like an idiot as I seem to constantly be learning and forgetting "good" C++ practice.

• idmean: Don't feel like an idiot: Forgetting is actually an important part of learning!
• Tolani: Could you clarify this line - "Specifically, what's the cleanest way to implement the Node class in data structures where we see something like this? this plays into how namespacing can get tricky."
• Bill Harper: I made a couple edits which hopefully clear things up a bit
• Captain Hatteras: About typename, it is required any time the compiler is unsure if something is a type or not. I won't go into details, but the compiler doesn't know if (for example std::remove_reference<T>::type is a type, because there might be a specific version of remove_reference with a certain T for which type isn't a type (it could be an enumeration value).

Answer 1

LinkedList Header

Don't use identifiers with a leading underscore:

#ifndef _NEW_LL_H
#define _NEW_LL_H

These two are not valid (reserved for the implementation).

Header inclusion order:

#include<memory>
#include "node.h"

I always do most specific to least. So your local header files first. Then C++ header files. Then C header files. Also add a space before <memory.h>.

Put the & with the type (its part of the type information).

 LinkedList(LinkedList const & ll); // copy constructor
 LinkedList& operator=(LinkedList const & ll); // copy assignment
 LinkedList(LinkedList && ll); // move constructor
 LinkedList& operator=(LinkedList && ll); // move assignment

You have a normal append.

 void append(T const& item);

But your list is move aware. So it seems like you should be able to move elements into the list.

 void append(T&& item);
 template<typename... Args>
 void append(Args&&... args); // append item but use its constructor.

Node Header

Don't use identifiers with a leading underscore:

#ifndef _NODE_H
#define _NODE_H

These two are not valid (reserved for the implementation).

You have normal constructors:

Node(T const& t); // default constructor
Node(Node const& insert); // copy constructor

But what about the move constructors.

Node(Node&& move);

Source File review:

Don't do this:

using namespace std;

Its short for a reason. Adding std:: as a prefix is not that much of a burden. Get used to it. Also worth a read Why is "using namespace std" considered bad practice?. It will explain in detail why it is bad practice.

This does not work if the source is empty.

template <typename T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList<T> const & ll) {
 if(ll.root) root = make_unique<Node>(*ll.root);
} // copy assignment

This means if you try and copy a list (that happens to be empty) nothing happens. Which is not what you want. If the source is empty then you want your list to become empty (not keep its current content). just convert to using the copy and swap idiom.

Prefer to use the initializer list than the body.

template <typename T>
LinkedList<T>::LinkedList(LinkedList<T> && ll) {
 root = move(ll.root);
} // move constructor

Here you are basically initializing root with nullptr then immediately assigning over it.

You can simplify this a lot. It should not matter if the root is nullptr or not. You are always adding to a thing that is unique_ptr<Node>. Just find the correct one then call make_unique()

template <typename T>
void LinkedList<T>::append(T const& item) {
 if(root==nullptr) {
 root = make_unique<Node<T>>(item);
 return;
 }
 Node<T> *tmpNode = root.get();
 while(tmpNode->next!=nullptr) tmpNode=tmpNode->next.get();
 tmpNode->next = make_unique<Node<T>>(item);
}

Your delete is basically a search() followed by a delete. Why not reduce redundant code by moving the search into its own private doSearch() function that returns a Node*. Then the public functions can use this private function and return the appropriate value.

template <typename T>
bool LinkedList<T>::delete_node(T const& item) {
 if(root->item == item) {
 root = move(root->next);
 return true;
 }
 Node<T> *tmpNode = root.get();
 while(tmpNode->next!=nullptr) {
 if(tmpNode->next->item == item) {
 tmpNode->next = move(tmpNode->next->next);
 return true;
 }
 tmpNode = tmpNode->next.get();
 }
 return false;
}

If you are going to print. Then a least allow the user to specify what stream you want to print too (you can provide a default version):

template <typename T>
void LinkedList<T>::print(std::ostream& out = std::cout)
{
}

Note the default way to print something in C++ is to use the operator<< so you may as well define one of those while you are at it:

frined std::ostream& operator<<(std::ostream& str, LinkedList const& list)
{
 list.print(str);
 return str;
}

Answer 2

In addition to what @MartinYork said, I have a few comments.

std::unique_ptr<typename Node<T>::Node> head;

Why don't you just say:

std::unique_ptr<Node<T>> head;

Inside a class, you don't have to specify any template parameters when using that class type. The compiler automatically assumes you are talking about LinkedList<T>.

Also, check out std::forward_list<T> here.