Circular linked list

Question

Please review this:

#include <iostream>
using namespace std;

template <class T>
struct Node
{
  T data;
  Node * next;
  Node(T data) : data(data), next(NULL) {}
};

template <class T>
class CircularLinkedList
{
public:
  CircularLinkedList() : head(NULL) {}
  ~CircularLinkedList();
  void addNode(T data);
  void deleteNode(T data);
  template <class U>
  friend std::ostream & operator<<(std::ostream & os, const CircularLinkedList<U> & cll);
private:
  Node<T> * head;
};

template <class T>
CircularLinkedList<T>::~CircularLinkedList()
{
  if (head)
    {
      Node<T> * tmp = head;
      while (tmp->next != head)
        {
          Node<T> * t = tmp;
          tmp = tmp->next;
          delete(t);
        }
      delete tmp;
      head = NULL;
    }
}

template <class T>
void CircularLinkedList<T>::addNode(T data)
{
  Node<T> * t = new Node<T>(data);

  if (head == NULL)
    {
      t->next = t;
      head = t;
      return;
    }

  Node<T> * tmp = head;
  while (tmp->next !=  head)
    {
      tmp = tmp->next;
    }

  tmp->next = t;
  t->next = head;
}

template <class T>
void CircularLinkedList<T>::deleteNode(T data)
{
  Node<T> * tmp = head;
  Node<T> * prev = NULL;
  while (tmp->next !=  head)
    {
      if (tmp->data == data) break;
      prev = tmp;
      tmp = tmp->next;
    }

  if (tmp == head)
    {
      while (tmp->next != head)
        {
          tmp = tmp->next;
        }
      tmp->next = head->next;
      delete head;
      head = tmp->next;
    }
  else
    {
      prev->next = tmp->next;
      delete tmp;
    }
}

template <class U>
std::ostream & operator<<(std::ostream & os, const CircularLinkedList<U> & cll)
{
  Node<U> * head = cll.head;
  if (head)
    {
      Node<U> * tmp = head;
      while (tmp->next != head)
        {
          os << tmp->data << " ";
          tmp = tmp->next;
        }
      os << tmp->data;
    }
  return os;
}

int main()
{
  CircularLinkedList<int> cll;

  cll.addNode(1);
  cll.addNode(2);
  cll.addNode(3);
  cll.addNode(4);
  cll.addNode(5);

  cout << cll << endl;

  cll.deleteNode(3);
  cll.deleteNode(1);
  cll.deleteNode(5);

  cout << cll << endl;

  return 0;
}

Answer 1

)

My first comment is you should start looking at smart pointers.
They will definitely simplify your code.

The second comment: look at the STL containers.
Containers in C++ follow a specific pattern. The idea is that we want to use algorithms on containers interchangeably and thus containers follow these conventions to make them easy to use with the standard algorithms.

Third comment: you fail to follow the rule of three.
Basically. If you define one of 'Destructor'/'Copy-Constructor'/'Assignment-Operator' (rather than using the compiler generated defaults) then you probably need to define all three. In this case your code is going to crash if you make a copy of the list. The problem arises from having an owned pointer in your code.

Fourth comment: Prefer to be pass parameters by const reference. For simple objects like integers it will not make any difference. But you have templatised the code and T can be any type. Thus passing by value is going to cause a copy (which may be expensive).

Reviewing the above code:
The complexity of adding a node is O(n). By maintaining a head and a tail pointer you can change this to have a complexity of O(1). ie. this loop becomes unnecessary.

Node<T> * tmp = head;
while (tmp->next !=  head)
{
  tmp = tmp->next;
}

You have an output operator std::ostream & operator<<(std::ostream & os, const CircularLinkedList<U> & cll) It would be nice if you had a symmetric input operator. In this situation you need to worry about the size of the list (or adding a special terminating character). So the creation of the input operator will affect your design of the output operator.

Answer 2

the code has problem when the list has only one node, and when it is removed, the head is not pointed to NULL.

e.g.,

int main() {
CircularLinkedList<int> cll;

cll.addNode(5);
cout << cll << endl;
cll.deleteNode(5);
cout << cll << endl;
return 0;
}

Answer 3

Also, for simplicity I would have kept a reference to the last inserted item (calling it the tail might be wrong as it is circular, but then again is concise with your head). This way, inserting would be O(1) instead of O(n), which makes sense as you know you will add it last in the list, right before head. You could then do:

if (head == NULL) {
    head = t;
    head->next = head;
    return;
}

tail->next = t;
t->next = head;

in add_node.