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.

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.