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);
}