Linked list with deep copy constructor

Question

I've created a linked list template class which contains a copy constructor that performs a deep copy of the list.

LinkedList.hpp

template <class T>
class LinkedList {
protected:
    struct Node {
        T value;
        Node *next;
        Node(T val, Node *nxt=NULL) {
            value = val;
            next = nxt;
        }
    };
    Node *head;
public:
    LinkedList();
    LinkedList(LinkedList &obj);
    ~LinkedList();

};

LinkedList.cpp

template <class T>
LinkedList<T>::LinkedList() {
    head = NULL;
}

template <class T>
LinkedList<T>::LinkedList(LinkedList &obj) {
    if (obj.head == NULL) {
        head = NULL;
    }
    else {
        head = new Node(obj.head->value);
        Node *current = head;
        Node *objHead = obj.head;
        Node *currentObj = objHead;
        while (currentObj->next != NULL) {
            current->next = new Node(currentObj->next->value);
            currentObj = currentObj->next;
            current = current->next;
        }
    }
}

template <class T>
LinkedList<T>::~LinkedList() {
    Node *current = head;
    while (current != NULL) {
        Node *garbage = current;
        current = current->next;
        delete garbage;
    }
}

template class LinkedList<int>;
template class LinkedList<double>;
template class LinkedList<bool>;
template class LinkedList<string>;

From what I can tell, the default copy constructor implements this functionality naturally, but I wanted to see if I could create a deep copy of a linked list myself using a self-defined copy constructor.

When I test this using:

LinkedList<int> ll;
ll.add(1);
ll.add(2);
ll.add(3);
ll.add(4);

LinkedList<int> ll2 = ll;
ll.add(5);

ll.displayList();
ll2.displayList();

It prints 1,2,3,4,5 and then 1,2,3,4. I believe this is correct. Are there any improvements I can make to the implementation of this?

Answer 1

A few fairly obvious points:

Prefer nullptr over NULL

Unless you really need to support older compilers, you're generally better off using nullptr in new code. If you do use nullptr, you can still support older compilers if really necessary--it's basically just a class that provides conversions for pointer to T and pointer to member.

Prefer member initializer lists over assignment in a constructor

The most obvious example here would be to replace your node constructor:

Node(T val, Node *nxt=NULL) {
    value = val;
    next = nxt;
}

...with one using a member initializer list:

Node(T value, Node *next = nullptr) :
    value(value),
    next(next)
{}

Note that yes, in this case, although the parameter being used to initialize it have the same name, but the compiler can keep track of which is which anyway.

Rule of three/five/zero

Note that in virtually every case, if you provide a destructor and a copy ctor, you also want a copy assignment operator. If you want the better efficiency you can get from move construction/move assignment available in C++11 and later, you'll probably want to add overloads of those that accept rvalue references. I consider it open to debate whether the rule of zero really applies well in this case--I've written a linked list that used smart pointers, but I was never entirely happy with it. It's clumsy but workable in the case of a singly linked list. For a doubly linked list, it's...basically unmanageable.

Side Note

Contrary to your statement, if you don't include a copy ctor, you probably won't get correct results with this sort of class. In particular, the compiler will generate code that does a shallow copy, so only the head pointer in the LinkedList object will be copied. This means if you copy a linked list, you'll end up with both pointing to a single head node. In itself that's not necessarily a problem, but when either of those is destroyed, all the nodes in the list will be destroyed, so in essence you've just destroyed both linked lists, not just the one you intended to. Attempting to use or destroy the one that wasn't supposed to have been destroyed yet will give undefined behavior.

Answer 2

Template definitions belong in headers

I suspect your test is also in LinkedList.cpp, yes? This'll prove to be a headache in the future. Definitions as part of a template class need to be available during object file generation, which is only possible if the definition is available in the same translation unit, such as by an included header file.

Prefer modern conventions

Assuming you're using a modern compiler, the C++ 11 standard should be the default unless you've (for some reason) specified otherwise. This has implications to your use of pointers.

• In modern code, prefer nullptr to NULL.
• Prefer smart pointers (such as std::unique_ptr) to raw pointers. This will add a measure of exception-safety to your copy constructor ---for those occassions in the future that you might use this template for non-primitive types--- and eliminates the need to define a custom dtor.

LinkedList.hpp

#include <iostream>
#include <memory>

template <class T>
class LinkedList {
protected:
    struct Node {
        T value;
        std::unique_ptr<Node> next;
 
        Node(const T& val, std::unique_ptr<Node>&& nxt=nullptr) {
            value = val;
            next = std::move(nxt);
        }

        Node(T&& val, std::unique_ptr<Node>&& nxt=nullptr) {
            value = std::move(val);
            next = std::move(nxt);
        }
    };

std::unique_ptr<Node> head;
std::unique_ptr<Node>* tail = &head;

public:
    LinkedList() = default;
    LinkedList(LinkedList& obj);
    LinkedList(LinkedList&& ) = default;
    ~LinkedList() = default;

    void add(const T& element);
    void add(T&& element);

    void displayList();
};

template<class T>
void LinkedList<T>::add(const T& element){
   *tail = std::make_unique<Node>(element);
   tail = &((**tail).next);
}

template<class T>
void LinkedList<T>::add(T&& element){
   *tail = std::make_unique<Node>(std::move(element));
   tail = &((**tail).next);
}

template<class T>
void LinkedList<T>::displayList(){
   Node* node = head.get();
   while(node){
       std::cout << node->value;
       if (node->next) std::cout << ", ";
       node = node->next.get();
   }
   std::cout << std::endl;
}

template<class T>
LinkedList<T>::LinkedList(LinkedList& obj){
   Node* node = obj.head.get();
   while(node){
       *tail = std::make_unique<Node>(node->value);
       node = node->next.get();
       tail = &((**tail).next);
   }
}

Live Example

As an aside, there are a methods listed in your test code not supported by the posted implementation. In the future, either exclude references to those methods from your example or include the relevant source.