Linked List implementation in C++

Question

I'm learning to implement linked list. I've implemented sorting with merge sort, reversing etc...

LinkedList.cpp

#include <iostream>
template <class T>
struct Node
{
 T data;
 Node * next;
};
template <class T>
class LinkedList
{
public:
 LinkedList() : head(NULL), size(0) {};
 ~LinkedList() { destroyList(); };
 bool addNode(T data);
 bool deleteNode(T data);
 Node<T> * searchNode(T data);
 void printList();
 void reverseList();
 void sortList();
private:
 Node<T> * head;
 int size;
 void destroyList();
 Node<T>* mergeSort(Node<T> * head, int total);
 Node<T>* Merge(Node<T>* left, int lcount, Node<T>* right, int rcount);
 void print(Node<T> * tmp);
};
template <class T>
bool LinkedList<T>::addNode(T data)
{
try
 {
 Node<T> * tmp = new Node<T>();
 tmp->data = data;
 tmp->next = head;
 head = tmp;
 ++size;
 return true;
 }
catch(std::exception & ex)
 {
 return false;
 }
}
template <class T>
bool LinkedList<T>::deleteNode(T data)
{
 Node<T> *curr = head, *prev = NULL;
 while (curr)
 {
 if (curr->data == data) break;
 prev = curr;
 curr = curr->next;
 }
 if (curr)
 {
 if (prev)
 {
 prev->next = curr->next;
 }
 else
 {
 head = curr->next;
 }
 delete(curr);
 --size;
 return true;
 }
 else
 {
 return false;
 }
}
template <class T>
Node<T> * LinkedList<T>::searchNode(T data)
{
 Node<T> * tmp = head;
 while (tmp)
 {
 if (tmp->data == data)
 {
 return tmp;
 }
 tmp = tmp->next;
 }
 return NULL;
}
template <class T>
void LinkedList<T>::print(Node<T> * tmp)
{
 bool printNewLine = (tmp) ? true : false;
 while (tmp)
 {
 std::cout << tmp->data << ",";
 tmp = tmp->next;
 } 
 if (printNewLine)
 {
 std::cout << std::endl;
 }
}
template <class T>
void LinkedList<T>::printList()
{
 Node<T> * tmp = head;
 bool printNewLine = (tmp) ? true : false;
 while (tmp)
 {
 std::cout << tmp->data << "|";
 tmp = tmp->next;
 } 
 if (printNewLine)
 {
 std::cout << std::endl;
 }
}
template <class T>
void LinkedList<T>::destroyList()
{
 Node<T> * tmp = NULL;
 while (head)
 {
 tmp = head;
 head = head->next;
 //std::cout << "deleting data " << tmp->data << std::endl;
 delete(tmp);
 }
}
template <class T>
void LinkedList<T>::reverseList()
{
 Node<T> *curr = head, *prev = head, *save = NULL;
 while (curr)
 {
 save = curr->next;
 curr->next = prev;
 prev = curr;
 curr = save;
 }
 head->next = NULL;
 head = prev;
}
//use merge sort
template <class T>
void LinkedList<T>::sortList()
{
 head = mergeSort(head, size);
}
template <class T>
Node<T>* LinkedList<T>::mergeSort(Node<T> * first, int total)
{
 if (total < 1) { return first; }
 if (total < 2) { first->next = NULL; return first;}
 Node<T> * curr = first;
 int count = total/2;
 while (count--)
 {
 curr = curr->next;
 }
 count = total/2;
 first = mergeSort(first, count);
 curr = mergeSort(curr, total-count);
 return Merge(first, count, curr, total-count);
}
template <class T>
Node<T>* LinkedList<T>::Merge(Node<T>* left, int lcount, Node<T>* right, int rcount)
{
 Node<T> * h = new Node<T>();
 h->next = NULL;
 Node<T> * tmp = h;
 while (lcount > 0 && rcount > 0)
 {
 if (left->data < right->data)
 {
 tmp->next = left;
 tmp = tmp->next;
 left = left->next;
 --lcount;
 }
 else if (right->data < left->data)
 {
 tmp->next = right;
 tmp = tmp->next;
 right = right->next;
 --rcount;
 }
 else
 {
 tmp->next = left;
 tmp = tmp->next;
 left = left->next;
 --lcount;
 tmp->next = right;
 tmp = tmp->next;
 right = right->next;
 --rcount;
 }
 }
 while (lcount > 0)
 {
 tmp->next = left;
 tmp = tmp->next;
 left = left->next;
 --lcount;
 }
 while (rcount > 0)
 {
 tmp->next = right;
 tmp = tmp->next;
 right = right->next;
 --rcount;
 }
 tmp = h;
 h = h->next;
 delete(tmp);
 return h;
}
int main()
{
 LinkedList<int> l;
 l.addNode(3);
 l.addNode(2);
 l.addNode(6);
 l.addNode(4);
 l.addNode(3);
 l.printList();
 l.reverseList();
 l.printList();
 l.sortList();
 l.printList();
 l.deleteNode(3);
 l.deleteNode(3);
 l.deleteNode(4);
 l.printList();
 l.reverseList();
 l.printList();
 l.sortList();
 l.printList();
 if (l.searchNode(2))
 {
 std::cout << "2 found \n";
 }
 if (!l.searchNode(5))
 {
 std::cout << "5 not found \n";
 }
 return 0;
}

• Winston Ewert: Welcome to code review! Please post the code you want reviewed as part of your post rather then a link to elsewhere.
• Aluan Haddad: Your code is asking for memory leaks by allocating a new node on the free store but neglecting to delete the node in the case of an exception. You should avoid this possibility altogether by using standard library smart pointer type such as std::unique_ptr<T>

Answer 1

#include <iostream>
template <class T>
struct Node
{
 T data;
 Node * next;
};
template <class T>
class LinkedList
{
public:
 LinkedList() : head(NULL), size(0) {};
 ~LinkedList() { destroyList(); };

Why did you make destroyList a seperate method? Why not put it in the destructor?

 bool addNode(T data);
 bool deleteNode(T data);
 Node<T> * searchNode(T data);
 void printList();
 void reverseList();
 void sortList();
private:
 Node<T> * head;
 int size;

I recommend some newlines between the data methods and the utility functions.

 void destroyList();
 Node<T>* mergeSort(Node<T> * head, int total);
 Node<T>* Merge(Node<T>* left, int lcount, Node<T>* right, int rcount);

I recommend picking a consistent capitalization scheme. This should be merge not Merge.

 void print(Node<T> * tmp);
};
template <class T>
bool LinkedList<T>::addNode(T data)
{
try
 {
 Node<T> * tmp = new Node<T>();
 tmp->data = data;
 tmp->next = head;
 head = tmp;
 ++size;
 return true;
 }
catch(std::exception & ex)
 {
 return false;
 }

Don't ever do this. You shouldn't generally catch all exceptions. You should catch only the exception you are interested in. Converting the exception into a return value loses the advantage of an exception. Why did you add this exception logic here? }

template <class T>
bool LinkedList<T>::deleteNode(T data)
{
 Node<T> *curr = head, *prev = NULL;

I recommend typing whole words not abbreviations.

 while (curr)
 {
 if (curr->data == data) break;

Use while(curr && curr->data != data)

 prev = curr;
 curr = curr->next;
 }
 if (curr)
 {

You are making use of inconsistent indentation. Pick a scheme and stick to it.

 if (prev)
 {
 prev->next = curr->next;
 }
 else
 {
 head = curr->next;
 }
 delete(curr);

Parenthesis not needed

 --size;
 return true;
 }
 else
 {
 return false;
 }
}
template <class T>
Node<T> * LinkedList<T>::searchNode(T data)

You are really finding a node rather then searching it.

{
 Node<T> * tmp = head;

tmp should be a banned variable name. all variables are temporary, so pick a better name,

 while (tmp)
 {

I suggest

for(Node * tmp = head; tmp; tmp = tmp->next)

I think it'll make the code clearer.

 if (tmp->data == data)
 {
 return tmp;
 }
 tmp = tmp->next;
 }
 return NULL;
}
template <class T>
void LinkedList<T>::print(Node<T> * tmp)

Printing is a bit of a odd feature for a linked list class. Typically, you'd except external code to handle that.

{
 bool printNewLine = (tmp) ? true : false;

Use 'bool printNewLine = bool(tmp)';

 while (tmp)
 {
 std::cout << tmp->data << ",";
 tmp = tmp->next;
 } 
 if (printNewLine)

Rather then doing this. I suggest keeping a copy of the original parameter and testing it here. { std::cout << std::endl; } }

Is the function even used?

template <class T>
void LinkedList<T>::printList()
{
 Node<T> * tmp = head;
 bool printNewLine = (tmp) ? true : false;
 while (tmp)
 {
 std::cout << tmp->data << "|";

|? Okay, whatever.

 tmp = tmp->next;
 } 
 if (printNewLine)
 {
 std::cout << std::endl;
 }
}
template <class T>
void LinkedList<T>::destroyList()
{
 Node<T> * tmp = NULL;
 while (head)
 {
 tmp = head;
 head = head->next;
 //std::cout << "deleting data " << tmp->data << std::endl;

Don't leave dead code in your code.

 delete(tmp);
 }
}
template <class T>
void LinkedList<T>::reverseList()
{
 Node<T> *curr = head, *prev = head, *save = NULL;
 while (curr)
 {
 save = curr->next;

You should declare save inside this loop rather then outside. I also suggest calling it next.

 curr->next = prev;
 prev = curr;
 curr = save;
 }
 head->next = NULL;
 head = prev;
}
//use merge sort
template <class T>
void LinkedList<T>::sortList()
{
 head = mergeSort(head, size);
}
template <class T>
Node<T>* LinkedList<T>::mergeSort(Node<T> * first, int total)
{
 if (total < 1) { return first; }
 if (total < 2) { first->next = NULL; return first;}
 Node<T> * curr = first;
 int count = total/2;

Add spaces around operators

 while (count--)

I suggest counting down via for loop { curr = curr->next; }

 count = total/2;

Rather then doing this calculation twice, I suggest saving the original version

 first = mergeSort(first, count);
 curr = mergeSort(curr, total-count);
 return Merge(first, count, curr, total-count);
}
template <class T>
Node<T>* LinkedList<T>::Merge(Node<T>* left, int lcount, Node<T>* right, int rcount)
{
 Node<T> * h = new Node<T>();
 h->next = NULL;
 Node<T> * tmp = h;

Creating a node during merging seems odd...

 while (lcount > 0 && rcount > 0)
 {
 if (left->data < right->data)
 {
 tmp->next = left;
 tmp = tmp->next;

use tmp = left

 left = left->next;
 --lcount;
 }
 else if (right->data < left->data)
 {
 tmp->next = right;
 tmp = tmp->next;
 right = right->next;
 --rcount;
 }
 else
 {
 tmp->next = left;
 tmp = tmp->next;
 left = left->next;
 --lcount;
 tmp->next = right;
 tmp = tmp->next;
 right = right->next;
 --rcount;

There is no need for this. Just let one of the above cases handle equal as well. } }

 while (lcount > 0)
 {
 tmp->next = left;
 tmp = tmp->next;
 left = left->next;
 --lcount;

This pattern is getting common. Think about refactoring this function or writing a function.

 }
 while (rcount > 0)
 {
 tmp->next = right;
 tmp = tmp->next;
 right = right->next;
 --rcount;
 }
 tmp = h;
 h = h->next;
 delete(tmp);
 return h;
}

EDIT: My version of merge

template <class T>
Node<T>* LinkedList<T>::Merge(Node<T>* left, int count_left, Node<T>* right, int count_right)
{
 Node<T> * head = NULL;
 Node<T> ** current = &head;
 while (count_left > 0 || count_right > 0)
 {
 if( count_right == 0 || (count_left > 0 && left->data < right->data))
 {
 *current = left;
 left = left->next;
 --count_left;
 }
 else
 {
 *current = right;
 right = right->next;
 --count_right;
 }
 current = &(*current)->next;
 }
 return head;
}

• Medicine: Helpful suggestions. Thanks. "There is no need for this. Just let one of the above cases handle equal as well." I think it is not possible because we have to advance both the lists in this case.
• Medicine: Creating a node during merging seems odd... while (lcount > 0 && rcount > 0) { if (left->data < right->data) { tmp->next = left; tmp = tmp->next; use tmp = left If I do tmp=left, how will I be able to advance the tmp correctly in the next iteration
• Winston Ewert: @Medicine, you'll be fine if you only advance one of the lists. The other value will still be there and you can advance it next time. I'll add how I'd do the merge.
• Medicine: right, I also wanted the sort to be stable. So, I should be handling the equality case to the left.
• Winston Ewert: @Medicine, ok. easy enough to do just change the < to <=