C++ Program to Implement a Circular Linked List

1. Introduction

A circular linked list is a variation of the standard linked list, wherein the last node's next pointer points back to the first node, effectively forming a loop. This structure is beneficial in scenarios where cyclic iterations are necessary, like in round-robin scheduling. 

In this post, we'll walk you through the process of creating a basic circular linked list in C++.

2. Program Overview

Our program will:

1. Define a Node structure for the circular linked list.

2. Implement a CircularLinkedList class with functions to:

- Add elements to the end of the list.

- Display the elements of the list.

- Count the number of nodes in the list.

3. Demonstrate these functions in the main program.

3. Code Program

#include<iostream>
using namespace std;

// Node structure for Circular Linked List
class Node {
public:
    int data;
    Node* next;

    // Constructor to initialize a new node
    Node(int val) {
        data = val;
        next = nullptr;
    }
};

class CircularLinkedList {
private:
    Node* head;

public:
    CircularLinkedList() {
        head = nullptr;
    }

    // Function to add a node to the end
    void append(int data) {
        Node* newNode = new Node(data);
        if (!head) {
            head = newNode;
            head->next = head;
        } else {
            Node* temp = head;
            while (temp->next != head) {
                temp = temp->next;  // Traverse to the last node
            }
            temp->next = newNode;
            newNode->next = head;
        }
    }

    // Function to display the list
    void display() {
        if (!head) return;
        Node* temp = head;
        do {
            cout << temp->data << " -> ";
            temp = temp->next;
        } while (temp != head);
        cout << "HEAD" << endl;
    }

    // Function to count nodes in the list
    int count() {
        if (!head) return 0;
        int cnt = 0;
        Node* temp = head;
        do {
            cnt++;
            temp = temp->next;
        } while (temp != head);
        return cnt;
    }
};

int main() {
    CircularLinkedList cll;
    cll.append(10);
    cll.append(20);
    cll.append(30);
    cout << "Circular Linked List: ";
    cll.display();
    cout << "Number of nodes: " << cll.count() << endl;
    return 0;
}

Output:

Circular Linked List: 10 -> 20 -> 30 -> HEAD
Number of nodes: 3

4. Step By Step Explanation

1. We define a Node class that represents each node in the linked list, containing the data and a next pointer.

2. Our CircularLinkedList class provides an interface for working with the linked list, including methods to append data, display the list, and count nodes.

3. The append method ensures that the newly added node is linked in such a way that the list remains circular.

4. The display method loops through the list and stops when it encounters the head node again.

5. Similarly, the count method counts the nodes until it comes back to the head.

6. In the main function, we demonstrate adding three nodes and display the list and its count.