Circular linked list

Please review this:

#include 
using namespace std;

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

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

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

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

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

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

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

template 
void CircularLinkedList::deleteNode(T data)
{
  Node * tmp = head;
  Node * 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 
std::ostream & operator & cll)
{
  Node * head = cll.head;
  if (head)
    {
      Node * tmp = head;
      while (tmp->next != head)
        {
          os data next;
        }
      os data;
    }
  return os;
}

int main()
{
  CircularLinkedList 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;
}

)

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 * tmp = head;
while (tmp->next !=  head)
{
  tmp = tmp->next;
}

You have an output operator std::ostream & operator & 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.

StackExchange Code Review Q#4628, answer score: 6