LinkedList with Node implementation

Question

Below is my implementation of templated Node and LinkedList classes. I would really appreciate it if someone would give me pointers on what I can improve.

//LinkedList with SumLists()

#include <iostream>
#include <set>

using namespace std;

template<class T>
class Node
{
public:
    T data;
    Node<T> * next;
    Node<T>(const T& d):data(d), next() {}
    Node<T>(const Node<T>& copyNode) : data(copyNode.data), next() {}

private:
    Node<T>& operator=(const Node<T>&);
};

template<class T>
class LinkedList
{
public:

    Node<T> * head;
    Node<T> * tail;

    LinkedList(const LinkedList& LL);
    LinkedList& operator=(LinkedList byValList);
    LinkedList(): head(NULL), tail(NULL) {}
    LinkedList(Node<T> * newNode) : head(newNode), tail(newNode) {}
    ~LinkedList();

    static LinkedList<int> sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2);

    void insertToTail(T val);
    void insertToHead(T val);
    void print();
    void printBackwards();
};

template<class T>
LinkedList<T>::LinkedList(const LinkedList<T>& LL) : head(NULL), tail(NULL)
{
    const Node<T> * curr = LL.head;

    if (!head && curr)
    {
        head = new Node<T>(curr->data);
        tail = head;
        curr = curr->next;
    }

    while (curr)
    {
        Node<T> * newNode = new Node<T>(curr->data);
        tail->next = newNode;
        tail = newNode;
        curr = curr->next;
    }
}

template<class T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList byValList)
{
    std::swap(head, byValList.head);
    return *this;
}

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

template<class T>
void LinkedList<T>::insertToTail(T val)
{
    Node<T> * newNode = new Node<T>(val);
    if (tail == NULL)
    {
        newNode->next = tail;
        tail = newNode;
        head = newNode;
        return;
    }
    tail->next = newNode;
    tail = tail->next;
}

template<class T>
void LinkedList<T>::insertToHead(T val)
{
    Node<T> * newNode = new Node<T>(val);
    newNode->next = head;
    head = newNode;
    if (head->next == NULL)
        tail = newNode;
}

template<class T>
void LinkedList<T>::print()
{
    Node<T> * curr = head;
    while (curr)
    {
        cout<<curr->data<<" --> ";
        curr = curr->next;
    }
    cout<<"NULL"<<endl;
}

template<class T>
void LinkedList<T>::printBackwards()
{
    Node<T> * curr;
    LinkedList ReversedList(new Node<T>(head->data));
    curr = head->next;
    while (curr)
    {
        ReversedList.insertToHead(curr->data);
        curr = curr->next;
    }

    curr = ReversedList.head;
    while (curr)
    {
        cout<<curr->data<<" --> ";
        curr = curr->next;
    }
    cout<<"NULL\n";
}

template<class T>
LinkedList<int> LinkedList<T>::sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2)
{
    Node<T>* curr1 = LL1.head;
    Node<T>* curr2 = LL2.head;

    LinkedList<int> ResultList;

    int newData;
    int carry = 0;

    while (curr1 && curr2)
    {
        newData = (curr1->data + curr2->data + carry) % 10;
        carry = (curr1->data + curr2->data + carry) / 10;
        ResultList.insertToTail(newData);

        curr1 = curr1->next;
        curr2 = curr2->next;
    }

    while (curr1 || curr2)
    {
        if (carry)
        {
            if (curr1)
                ResultList.insertToTail(curr1->data + carry);
            if (curr2)
                ResultList.insertToTail(curr2->data + carry);
            carry = 0;
            continue;
        }
        if (curr1)
        {
            ResultList.insertToTail(curr1->data);
            curr1 = curr1->next;
        }
        if (curr2)
        {
            ResultList.insertToTail(curr2->data + carry);
            curr2 = curr2->next;

        }


    }

    return ResultList;
}

int main()
{
    LinkedList<int> LL1(new Node<int>(7));
    LL1.insertToTail(1);
    LL1.insertToTail(6);
    LL1.insertToTail(5);
    LL1.insertToTail(4);

    LinkedList<int> LL2(new Node<int>(5));
    LL2.insertToTail(9);
    LL2.insertToTail(2);

    LinkedList<int> LL = LL1.sumLists(LL1, LL2);
    LL.print();
    LL2.print();
    LL = LL2;
    LL.print();
    LL2.print();

    return 0;
}

Answer 1

Please. Oh please stop doing this.

using namespace std;

If this was a header file you just polluted the global namespace for anybody that uses your file. This will get it banned from any serious project. This is done in textbooks for some reason and is fine for short ten line example programs. But once you get past 10 lines it has issues. Stop using it; it is a bad habbit that will get you into real problems on any decent sized project.

Why is “using namespace std;” considered bad practice?

You do really the standard library is in the namespace std. So it only costs you 5 extra characters to use it.

std::list<T>    myList;

Node is an implementation detail of the list. There is no reason for anybody using the list to know exactly how you implemented. Nor is there a reason to provide them with a Node class (as you will now need to maintain that concept).

template<class T>
class Node
{
public:
    T data;
    Node<T> * next;
    Node<T>(const T& d):data(d), next() {}
    Node<T>(const Node<T>& copyNode) : data(copyNode.data), next() {}

private:
    Node<T>& operator=(const Node<T>&);
};

So I would make Node a private member of LinkedList.

Its not really a copy constructor if you don't copy the next member.

Node<T>(const Node<T>& copyNode) : data(copyNode.data), next() {}

But OK. I can see this as an optimization. But personally I would have used a third constructor.

Node<T>(const Node<T>& copyNode, Node<T>* next)
    : data(copyNode.data)
    , next(next) 
{}

Then you can pass NULL as the second parameter, to initialize next.

So you have disabled the assignment operator:

private:
    Node<T>& operator=(const Node<T>&);

This is correct in C++03. But this is 2014 and C++11 is supported by all modern compilers and most already support C++14. So you should start using the modern version of the language.

    Node<T>& operator=(const Node<T>&) = delete;

Your implementation of linked list uses NULL as a terminator (which is fine). But if you add a fake sentinel value to your list it makes the implementation much easier as you never have NULL pointers (and end points at the sentinel).

In the copy constructor:

    if (!head && curr)

At this point head is always NULL. You just set it two lines above.

The other thing to note about the copy is that it will leak if you throw an exception. Since you don't know what the type of T is you have no idea how it will react to being copied. If halfway through the copy it throws an exception you should clean up any memory allocated so far before letting the exception propagate out of the constructor.

You are on the correct track with the assignment operator.

template<class T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList byValList)
{
    // BUT this line is not enough
    //     Assignment should make a copy of all the elements.
    std::swap(head, byValList.head);


    // Usually this is implemented as:
    // Now you need to write a version of swap for this class
    // (both member and free standing)
    byValList.swap(*this);

    return *this;
}

I would write them like this:

template<class T>
LinkedList<T>::swap(LinkedList<T>& rhs) noexcept // swap is supposed to be 
{                                                // free from exception
    std::swap(head,  rhs.head);                  // throwing
    std::swap(tail,  rhs.tail);
}

template<class T>
void swap(LinkedList<T>& lhs, LinkedList<T>& rhs) {lhs.swap(rhs);}

In the destructor:
You don't use curr to do anything useful. Remove it.

    Node<T> * curr = head;

        curr = head;

In your insert methods. I personally would return a reference to *this (see below). But in both your insert methods you check for empty is always a bit weird before assigning the other end. I would break the test for empty into its own method empty() then you can test empty() before doing your special case code.

template<class T>
LinkedList<T>& LinkedList<T>::insertToTail(T val);

This allows you to use operator chaining.

LinkedList<T>  list;
list.insertToTail(1).insertToTail(2).insertToTail(3);

Nothing wrong with a print method. But I would do three additional things. As the print() method does not modify the content of the list it should be marked as const. Rather than always printing to std::cout I would pass the output stream as a parameter (it can default to std::cout when none is provided. I would also write the output operator operator<< as that is the normal way of printing in C++.

template<class T>
void LinkedList<T>::print(std::ostream& stream = std::cout) const;

std::ostream& operator<<(std::ostream& stream, LinkedList<T> const& data)
{
    data.print(stream);
    return stream;
}

That's an expensive print when done backwards.
But once you have the list reversed. Why not re-use your standard print function?

template<class T>
void LinkedList<T>::printBackwards(std::ostream& stream = std::cout) const
{
     LinkedList<T>  rev;
     for(Node<T>* curr = rev.head; curr != NULL; curr = curr->next)
     {    rev.insertToHead(curr->data);
     }
     rev.print(stream);
}

Finally. In the sumLists. Its fine upto the point. where one list is empty. But the second part where one list is empty is over complex and you have a lot of nested ifs. Why not check and do each list individually.

template<class T>
LinkedList<int> LinkedList<T>::sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2)
{
    // First part good.

    // Only one is true.
    // But if you look at the code it is neater.
    // and more self contained.
    while (curr1)
    {
        if (carry)
        {
            ResultList.insertToTail(curr1->data + carry);
            carry = 0;
            continue;
        }
        ResultList.insertToTail(curr1->data);
        curr1 = curr1->next;
    }

    while (curr2)
    {
        if (carry)
        {
            ResultList.insertToTail(curr2->data + carry);
            carry = 0;
            continue;
        }
        ResultList.insertToTail(curr2->data + carry);
        curr2 = curr2->next;
    }
}

You will also notice that the two loops are very similar. So you can break that code into a separate method and call it twice.

template<class T>
LinkedList<int> LinkedList<T>::sumLists(const LinkedList<int>& LL1, LinkedList<int>& LL2)
{
    // First part good.

    // Only one is true.
    // But if you look at the code it is neater.
    // and more self contained.
    AddStuffToListOne(curr1, ResultList);
    AddStuffToListOne(curr2, ResultList);

}

Answer 2

Some observations:

Your data should (probably) be private. Otherwise, an enterprising developer will do this:

LinkedList<int> l;
// naively delete contents of l
delete l.head;

Node is an implementation detail of the list. It makes no sense to define it outside the class.

That means, the code should look like this:

template<class T>
class LinkedList
{
// private:
    struct Node // Node is a private implementation detail
    {
        T data;
        Node *next;
        Node(const T& d):data(d), next() {}
        Node(const Node& copyNode) : data(copyNode.data), next() {}

    private:
        Node& operator=(const Node&);
    };
    Node* head;
    Node* tail;

public:
    // ... rest of code here
};

After making head and tail private, you will need to add iteration and/or data retrieval API to your class.

When designing a class, consider how you will look at it from the perspective of client code, not how it is implemented (i.e. you are implementing a "list of instances of T", not a "list of instances of Node"). That means you should not have a constructor receiving a Node*, but a constructor receiving a T instance.

Your print and printBackwards functions should (probably) receive the output stream as a parameter (then, you can use the same code to print to a std::ostringstream, std::fstream, std::cout and so on).

Your copy&swap implementation of assignment should be written like this:

template<class T>
LinkedList<T>& LinkedList<T>::operator=(LinkedList byValList)
{
    using std::swap;        // enable ADL
    swap(*this, byValList); // implementation swaps by moving if there's a
                            // LinkedList<T>::LinkedList<T>(LinkedList<T>&&)
                            // defined; (consider defining it)

    return *this;
}

This function could use a std::move:

template<class T>
void LinkedList<T>::insertToTail(T val)
{
    Node<T> * newNode = new Node<T>(std::move(val)); // <<<<< 
    // ... 
}

For a POD-type T it's fine without it, but what happens if I write

LinkedList<std::string> l;
std::string s{' ', 10000};
l.insertToTail(s); // creates one copy of s for argument, and one for the node

Answer 3

I suspect there is a BUG in sumLists:

The following part

if (carry)
{
    if (curr1)
        ResultList.insertToTail(curr1->data + carry);
    if (curr2)
        ResultList.insertToTail(curr2->data + carry);
    carry = 0;
    continue;
}

should be replaced with

if (carry)
{
    if (curr1)
    {
        ResultList.insertToTail(curr1->data + carry);
        curr1 = curr1->next;
    }
    if (curr2)
    {
        ResultList.insertToTail(curr2->data + carry);
        curr2 = curr2->next;
    }
}