Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Please code review

#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;
}
share|improve this question
    
Most of the cases I wrote for your other question are also applicable here: codereview.stackexchange.com/questions/4629/… –  loki2302 Sep 7 '11 at 6:33
    
Use const reference instead of value –  fasked Sep 6 '12 at 21:47
add comment

3 Answers

up vote 5 down vote accepted

)

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.

share|improve this answer
    
I don't really see how smart pointers will help this code. In my mind, the most compelling reasons to use smart pointers are for exception safety and graceful cleanup. Here we have exactly 1 place where allocations happen. It's pretty manageable. I see the use of smart pointers here as a solution in need of a problem. Using smart pointer poorly would also make it worse, i.e. using shared_ptr would add gross amounts of overhead. –  asveikau Sep 8 '11 at 3:59
add comment

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;
}
share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.