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>
{
public:

Node<T> * tail;

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

template<class T>
{
const Node<T> * curr = LL.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>
{
return *this;
}

template<class T>
{
{
delete curr;
}
}

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

template<class T>
{
Node<T> * newNode = new Node<T>(val);
tail = newNode;
}

template<class T>
{
while (curr)
{
cout<<curr->data<<" --> ";
curr = curr->next;
}
cout<<"NULL"<<endl;
}

template<class T>
{
Node<T> * curr;
while (curr)
{
curr = curr->next;
}

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

template<class T>
{

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()
{
LL1.insertToTail(1);
LL1.insertToTail(6);
LL1.insertToTail(5);
LL1.insertToTail(4);

LL2.insertToTail(9);
LL2.insertToTail(2);

LL.print();
LL2.print();
LL = LL2;
LL.print();
LL2.print();

return 0;
}

-
Thanks Morwenn! –  Yechiel Labunskiy Feb 27 '14 at 13:50
@Morwenn note that partial code reviews are perfectly fine! –  Quentin Pradet Feb 27 '14 at 16:28
By the way, you can remove #include <set> since it's used nowhere in the code. –  Morwenn Feb 28 '14 at 15:58

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>
{
// BUT this line is not enough
//     Assignment should make a copy of all the elements.

// 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>
{                                                // free from exception
std::swap(tail,  rhs.tail);
}

template<class T>


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

    Node<T> * 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>


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
{
for(Node<T>* curr = rev.head; curr != NULL; curr = curr->next)
}
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>
{
// 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>
{
// First part good.

// Only one is true.
// But if you look at the code it is neater.
// and more self contained.

}

-
Thank you so much for taking the time for such a thorough review. This will be very helpful for me in improving my C++ programming. –  Yechiel Labunskiy Feb 27 '14 at 16:53
Loki, what do I need the free-standing swap function for? –  Yechiel Labunskiy Feb 27 '14 at 18:30
The free standing swap help for Kernig look-up (AKA ADL look-up). If you write: swap(ll1, ll2); where ll1 and ll2 are LinkedList<int> Then it will using Kernig look-up to find your swap implementation which is better than the default swap. –  Loki Astari Feb 27 '14 at 21:09
For being such a long standing contributor to this site, I don't think I have ever invited you to the chat room. Feel free to come and talk to the regulars sometime. :) –  syb0rg Feb 28 '14 at 3:40

Some observations:

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

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


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>
{
// 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* 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>
{
swap(*this, byValList); // implementation swaps by moving if there's a
// defined; (consider defining it)

return *this;
}


This function could use a std::move:

template<class T>
{
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

-
implementation swaps by moving if there is a move constructor. Otherwise it does it by copying. By default there is not a move constructor. –  Loki Astari Feb 27 '14 at 16:15
@LokiAstari, I hadn't known that (have an upvote :)). –  utnapistim Feb 27 '14 at 16:42
Thank you for your review –  Yechiel Labunskiy Feb 27 '14 at 16:54