How to Implement a Circular Linked List Data Structure in C++

1. Implement a Circular Singly Linked List with Member Functions to Add New Elements at the End and to Print Elements in C++
2. Implement the Destructor and Member Function to Insert New Elements at The Beginning of The List in C++

This article will explain how to implement a circular linked list data structure in C++.

Implement a Circular Singly Linked List with Member Functions to Add New Elements at the End and to Print Elements in C++

A circular linked list can be characterized as a linked list where the last node points to the head of the list. Essentially, nodes in the list form a circle, and there is no nullptr to demarcate the end of the list. You can utilize circular linked lists to build queue-style data structures. The circularity feature can be added to both the doubly linked list and a singly linked list.

In this case, we’re going to implement the latter one. Remember that we need to define a node structure that includes a pointer to the next node, and a data element to construct a singly linked list. The struct ListNode object represents a single node for our implementation and stores a single string object named data, which will serve as the element data for this example. Note that one can store any custom-defined object in a node, and if the object is relatively larger, it’s better to include it as a pointer.

Once we have a structure of a single node, we can define a CircularList class, which has only two member functions for starters. Generally, a circular linked list should keep track of the head of the list or its end; however, the implementer is usually free to make the class design decision based on their needs. Additionally, the CircularList class stores two separate pointers to represent the head and the end of the list.

The pointer that stores the head/end of the list can be a dummy node or an actual node with the data. In this example, we chose to design the CircularList class to have no dummy pointers. We defined a constructor to accept a string parameter to initialize the first node in the circular list. Note that design choices during class definition usually affect different variables, which should be considered based on the underlying problem. Thus, the following implementation is only meant to be a simple one for explaining the concept of circular linked lists.

Once the CircularList object is initialized using the constructor, we can add new elements using the insertNodeEnd member function. The latter accepts the string parameter and constructs a new element at the end of the list. The insertNodeEnd function allocates new elements with the new operator and modifies the pointers accordingly to insert the node just after the end of the list. It also updates the end data member to point to a newly allocated node.

Another member function defined in the next sample is the printNodes, which iterates through the list to print its contents and does not take any arguments. Now, to better demonstrate the usage of this structure, we need some driver code in the main function. We chose to initialize a vector of arbitrary strings later to be inserted into the CircularList object using the for loop. Finally, we invoke a printNodes function to display the list contents to the terminal.

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct ListNode {
  struct ListNode *next = nullptr;
  string data;
} typedef ListNode;

class CircularList {
 public:
  explicit CircularList(string data) {
    head = new ListNode;
    head->next = head;
    head->data = std::move(data);
    end = head;
  };

  ListNode *insertNodeEnd(string data);
  void printNodes();

 private:
  ListNode *head = nullptr;
  ListNode *end = nullptr;
};

ListNode *CircularList::insertNodeEnd(string data) {
  auto new_node = new ListNode;
  new_node->next = end->next;
  new_node->data = std::move(data);

  end->next = new_node;
  end = end->next;
  return new_node;
}

void CircularList::printNodes() {
  auto count = 0;
  auto tmp = head;
  while (tmp != end) {
    cout << "node " << count << " - data: " << tmp->data << endl;
    tmp = tmp->next;
    count++;
  }
  cout << "node " << count << " - data: " << tmp->data << endl;
}

int main() {
  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  CircularList clist("Xenial");

  for (const auto &item : data_set) {
    clist.insertNodeEnd(item);
  }

  clist.printNodes();

  return EXIT_SUCCESS;
}

Output:

node 0 - data: Xenial
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring

Implement the Destructor and Member Function to Insert New Elements at The Beginning of The List in C++

Notice that the previous code snippet has a huge issue of not having a destructor defined; this implies that the program utilizing the CircularList class will leak memory since the nodes created on the dynamic memory are not freed until the program exit.

The solution to this problem is to implement a destructor that will traverse the whole list and deallocate all the nodes using the delete operator. Thus, we don’t need to worry about freeing the list memory manually. It will be automatically freed once the CircularList object will reach the end of scope.

Another useful function to implement is the one that inserts a new element at the head of the list; the insertNodeHead command is designed to do just that. It takes only a string argument to be stored and returns the pointer to the newly allocated node. Note that the return value for the insertNodeEnd and insertNodeHead functions is another design choice, which is implemented differently as the programmer decides. The following code snippet includes the similar driver code in the main function to test and showcase the CircularList class usage.

#include <iostream>
#include <string>
#include <vector>

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

struct ListNode {
  struct ListNode *next = nullptr;
  string data;
} typedef ListNode;

class CircularList {
 public:
  explicit CircularList(string data) {
    head = new ListNode;
    head->next = head;
    head->data = std::move(data);
    end = head;
  };

  ListNode *insertNodeEnd(string data);
  ListNode *insertNodeHead(string data);
  void printNodes();

  ~CircularList();

 private:
  ListNode *head = nullptr;
  ListNode *end = nullptr;
};

ListNode *CircularList::insertNodeEnd(string data) {
  auto new_node = new ListNode;
  new_node->next = end->next;
  new_node->data = std::move(data);

  end->next = new_node;
  end = end->next;
  return new_node;
}

ListNode *CircularList::insertNodeHead(string data) {
  auto new_node = new ListNode;
  new_node->next = end->next;
  new_node->data = std::move(data);

  end->next = new_node;
  head = end->next;
  return new_node;
}

CircularList::~CircularList() {
  while (head != end) {
    auto tmp = head;
    head = head->next;
    delete tmp;
  }
  delete head;
}

void CircularList::printNodes() {
  auto count = 0;
  auto tmp = head;
  while (tmp != end) {
    cout << "node " << count << " - data: " << tmp->data << endl;
    tmp = tmp->next;
    count++;
  }
  cout << "node " << count << " - data: " << tmp->data << endl;
}

int main() {
  vector<string> data_set = {"Precise", "Quantal", "Saucy", "Raring"};

  CircularList clist("Xenial");

  for (const auto &item : data_set) {
    clist.insertNodeEnd(item);
  }

  clist.printNodes();
  cout << " ----------------------------------- " << endl;

  clist.insertNodeHead("Bionic");
  clist.insertNodeEnd("Zeisty");
  clist.printNodes();

  return EXIT_SUCCESS;
}

Output:

node 0 - data: Xenial
node 1 - data: Precise
node 2 - data: Quantal
node 3 - data: Saucy
node 4 - data: Raring
 -----------------------------------
node 0 - data: Bionic
node 1 - data: Xenial
node 2 - data: Precise
node 3 - data: Quantal
node 4 - data: Saucy
node 5 - data: Raring
node 6 - data: Zeisty