Circular Linked List implementation in C++

Question

I want to improve this code.

#include <iostream>
#include <utility>

template <class T>
class circular_linked_list
{
  struct Node
  {
    T data;
    Node * next;
    Node(T value) : data(std::move(value)), next(nullptr) {}
  };
  Node *head;

public:
  circular_linked_list() : head(nullptr) {}
  circular_linked_list(const circular_linked_list& cll) = delete; //copy constructor
  circular_linked_list(circular_linked_list&& cll) = delete; //move constructor
  circular_linked_list& operator=(const circular_linked_list& cll) = delete; //copy assignment
  circular_linked_list& operator=(circular_linked_list&& cll) = delete; //move assignment
  ~circular_linked_list();
  void insert_at_begin(T);
  void insert_at_end(T);
  void delete_node(T);
  void print_list();

private:
  struct Node *search(T value)
  {
    Node *node = head;
    while(node->next != head)
    {
      if(node->data == value)
        return node;

      node = node->next;
    }
    std::cerr << "No such element in the List \n";
    return nullptr;
  }
};

template <class T>
void circular_linked_list<T>::insert_at_begin(T value)
{
  Node *node = new Node(std::move(value));
  if(head == nullptr)
  {
    node->next = node;
    head = node;
    return;
  }
  Node *tmp = head;
  while(tmp->next != head)
  {
    tmp = tmp->next;
  }
  tmp->next = node;
  node->next = head;
  head = node;
}

template <class T>
void circular_linked_list<T>::insert_at_end(T value)
{
  Node *node = new Node(std::move(value));
  if(head == nullptr)
  {
    node->next = node;
    head = node;
    return;
  }
  Node *tmp = head;
  while(tmp->next != head)
  {
    tmp = tmp->next;
  }
  tmp->next = node;
  node->next = head;
}

template <class T>
void circular_linked_list<T>::delete_node(T value)
{
  Node *node = search(value);
  Node *tmp = head;
  Node *tail = head;
  while(tail->next != head)
  {
    tail = tail->next;
  }

  if(tmp == node)
  {
    head = tmp->next; //deleting first element
    tail->next = head;
  }
  else
  {
    while(node != nullptr)
    {
      if(tmp->next == node)
      {
        tmp->next = node->next;
        return;
      }
      tmp = tmp->next;
    }
  }
  delete tmp;
}

template <class T>
void circular_linked_list<T>::print_list()
{
  Node *tmp = head;
  while(tmp->next != head)
  {
    std::cout << tmp->data << ' ';
    tmp = tmp->next;
  }
  std::cout << tmp->data << '\n';
}

template <class T>
circular_linked_list<T>::~circular_linked_list()
{
  Node *tmp = nullptr;
  Node *tail = head;
  while(tail->next != head)
  {
    tail = tail->next;
  }
  tail->next = nullptr;

  while(head != nullptr)
  {
    tmp = head;
    head = head->next;
    delete tmp;
  }
}

int main()
{
  circular_linked_list<int> cll1;
  cll1.insert_at_end(2);
  cll1.insert_at_end(3);
  cll1.insert_at_end(4);
  cll1.insert_at_begin(1);
  cll1.insert_at_begin(0);
  cll1.print_list();
  cll1.delete_node(2);
  cll1.print_list();
}

Answer 1

Design

With a singly linked list it is O(n) to find the end (assuming you store the beginning). So it is often nice to track both the beginning and end of the list inside the list object.

Personally I would have gone with a doubly linked list (next/prev). That way you can store just the head but finding the tail (on a circular list) is simply getting the link before the head.

// Head of a list
list->head

// Tail of a list (doubly linked)
list->head->prev;

Another thing you should consider is a sentinel link. This is a link in the list that does not contain data but is always there. Note: The list is empty when it only contains the sentinel element. The advantage to using a sentinel node is that you don't have to worry about nullptr when traversing the list. This drastically reduces the amount of code you need to write.

So from that long description two changes I would make.

1. Doubly linked list next/prev
2. Add a sentinel node.

Code Review

Move and Copy

I see you deleted the copy/move operations. Fine if you are still working through it. But in the end you will need to implement these. These are actually quite simple when you learn the tricks (idioms).

As a simple helpping hand:

circular_linked_list(const circular_linked_list& cll)
// This you need to implement in full.
// I leave the details to you (but a full deep copy of the list is needed).

// The assignment operator is easy.
// It is implemented in terms of the copy constructor.
// And the swap operation.
circular_linked_list& operator=(const circular_linked_list& cll)
{
    circular_linked_list    copy(cll);   // Make a copy.
    swap(copy);                          // Call the swap method.
    return *this;
    // Small improvement can be made (look up copy and swap idiom).
}


// Move is easily implemented using a swap.
circular_linked_list(circular_linked_list&& cll) noexcept // dont forget the noexcept
     // Dont forget to initialize the members correctly.
 {
     // Swapping implements the requirements of move.
     // It also provided deferred deletion (which is a nice side affect)
     // allowing potential reuse of memory. But usually the object
     // will be correctly and normally destroyed.
     // It also provides the strong exception guarantee.
     swap(cll);
 }

 circular_linked_list& operator=(circular_linked_list&& cll) noexcept
 {
     swap(cll);
     return *this;
 }

 void swap(circular_linked_list& other) noexcept
 {
     using std::swap;
     // Implement the swap of all members for other into this.
 }

 friend void swap(circular_linked_list& lhs, circular_linked_list& rhs)
 {
      lhs.swap(rhs);
 }

Don't need an explicit constructor here.

  struct Node
  {
    T data;
    Node * next;
    Node(T value) : data(std::move(value)), next(nullptr) {}
  };

If you use the brace initializer you don't need an explicit initializer as long as you use put the members in order.

  Node* node = new Node{ 12, nullptr };

But you may want to explore some alternative constructors.

  // copy Cosntruct node.
  Node(T const& value);        // Pass by const reference and copy in
  Node(T&& value);             // Pass by r-value ref and move in
  template<typename... P>
  Node(P&&... args);           // Pass using the arguments that constructor 
                               // T allowing construction in place.

Printing

This is fine.

  void print_list();

But in C++ we usually print using the operator<<. So it is nice to define this operator for your class. Also std::cout is not the only stream you can print too (Files/Strings are two that pop out but lot of things are emulated like streams).

  void print_list(std::ostream& str = std::cout) const;
  friend std::ostream& operator<<(std::ostream& str, circular_linked_list const& data)
  {
       data.print_list(str);
       return str;
  }

Perfectly good search.

  struct Node *search(T value)
  {
    Node *node = head;
    while(node->next != head)
    {
      if(node->data == value)
        return node;

      node = node->next;
    }

But this may have been easier to write as a for loop:

    for(Node *node = head; node->next != head; node = node->next)
    {
      if(node->data == value) {
        return node;
      }
    }

Insert

Both insert operations have a lot of shared code. It would be better if you factor out the shared code into a separate function.

As noted in the design section. The code can be highly simplified by using a sentinel node. Also the loop to find the end should be removed by either using an end marker in the list or by using a doubly linked list.

Quick exit from delete.

If this returns nullptr then is there any reason to continue?

  Node *node = search(value);

Lot of extra work in delete.
I don't think you actually need tail.

Bug in print.

If the list is empty then your print is going to hit several places where it de-references a nullptr.

Destructor can be simplified.

You only need to loop over the list once to delete it. You don't need to unlink the tail from the head to make it work. Comparing pointers will still work after a pointer has been deleted. You just can't de-reference it after deleting.

template <class T>
circular_linked_list<T>::~circular_linked_list()
{
    Node* last = nullptr;
    Node* next
    for(Node* loop = head; loop != last; loop = next) {
        last = head;
        next = head->next;
        delete loop;
    }
}