Linked List implementation in C++

Question

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

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

Welcome to code review! Please post the code you want reviewed as part of your post rather then a link to elsewhere. — Winston Ewert, Commented Sep 4, 2011 at 3:32
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> — Aluan Haddad, Commented Sep 22, 2016 at 17:45

Winston Ewert · Accepted Answer · 2011-09-04 23:48:57Z

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

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, Commented Sep 4, 2011 at 14:08
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 — Medicine, Commented Sep 4, 2011 at 14:22
@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. — Winston Ewert, Commented Sep 4, 2011 at 15:01
right, I also wanted the sort to be stable. So, I should be handling the equality case to the left. — Medicine, Commented Sep 4, 2011 at 15:06

Stack Exchange Network

Linked List implementation in C++

1 Answer 1

Not the answer you're looking for? Browse other questions tagged
c++
linked-list
or ask your own question.

Hot Network Questions

Linked List implementation in C++

1 Answer 1

Not the answer you're looking for? Browse other questions tagged c++linked-list or ask your own question.

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
c++
linked-list
or ask your own question.