C++ Program to Implement a Circular Linked List

Table of Contents

Introduction

A Circular Linked List is a variation of the traditional linked list in which the last node points back to the first node, creating a circular structure. This design allows for efficient traversal, especially in applications where cyclic patterns are common, such as in round-robin scheduling or managing a playlist of songs. This article provides a comprehensive guide to implementing a circular linked list in C++, demonstrating various operations through multiple examples.

Prerequisites

Before diving into the implementation, you should have:

Basic understanding of C++ programming.
Familiarity with pointers and dynamic memory allocation.
Knowledge of linked lists and their basic operations.

With these prerequisites, you will be able to grasp the concepts and code implementations discussed here.

1. Basic Circular Linked List Implementation

1.1 Node Structure and List Initialization

Let’s start by defining the structure of a node in the circular linked list and initializing the list.

C++

#include <iostream>

struct Node {
    int data;
    Node* next;

    Node(int val) : data(val), next(nullptr) {}
};

class CircularLinkedList {
public:
    CircularLinkedList() : head(nullptr) {}

    void insertAtEnd(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
            head->next = head;
        } else {
            Node* temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            temp->next = newNode;
            newNode->next = head;
        }
    }

    void display() {
        if (head == nullptr) return;
        Node* temp = head;
        do {
            std::cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head);
        std::cout << std::endl;
    }

private:
    Node* head;
};

int main() {
    CircularLinkedList list;
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.insertAtEnd(40);

    std::cout << "Circular Linked List: ";
    list.display();

    return 0;
}

1.2 Output Explanation

In this example, the circular linked list is structured as follows:

C++

10 -> 20 -> 30 -> 40 -> (back to 10)

The output will display: 10 20 30 40

2. Advanced Circular Linked List Operations

2.1 Insertion at Beginning

Let’s add a method to insert a node at the beginning of the list.

C++

class CircularLinkedList {
    // ... (previous code remains the same)

public:
    void insertAtBeginning(int data) {
        Node* newNode = new Node(data);
        if (head == nullptr) {
            head = newNode;
            head->next = head;
        } else {
            Node* temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            newNode->next = head;
            temp->next = newNode;
            head = newNode;
        }
    }
};

int main() {
    CircularLinkedList list;
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.insertAtBeginning(10);
    list.insertAtEnd(40);
    list.insertAtBeginning(5);

    std::cout << "Circular Linked List after insertions: ";
    list.display();

    return 0;
}

2.2 Output Explanation

In this example, the circular linked list after the insertions is structured as follows:

C++

5 -> 10 -> 20 -> 30 -> 40 -> (back to 5)

The output will display: 5 10 20 30 40

3. Deletion in Circular Linked List

3.1 Deletion of a Specific Node

Next, we will implement a method to delete a specific node from the list.

C++

class CircularLinkedList {
    // ... (previous code remains the same)

public:
    void deleteNode(int key) {
        if (head == nullptr) return;

        Node *current = head, *prev = nullptr;
        while (current->data != key) {
            if (current->next == head) {
                std::cout << "Node not found" << std::endl;
                return;
            }
            prev = current;
            current = current->next;
        }

        if (current->next == head && prev == nullptr) {
            head = nullptr;
            delete current;
            return;
        }

        if (current == head) {
            prev = head;
            while (prev->next != head) {
                prev = prev->next;
            }
            head = current->next;
            prev->next = head;
            delete current;
        } else if (current->next == head) {
            prev->next = head;
            delete current;
        } else {
            prev->next = current->next;
            delete current;
        }
    }
};

int main() {
    CircularLinkedList list;
    list.insertAtEnd(10);
    list.insertAtEnd(20);
    list.insertAtEnd(30);
    list.insertAtEnd(40);

    std::cout << "Circular Linked List: ";
    list.display();

    list.deleteNode(20);
    std::cout << "List after deleting 20: ";
    list.display();

    list.deleteNode(10);
    std::cout << "List after deleting 10: ";
    list.display();

    return 0;
}

3.2 Output Explanation

In this example, the circular linked list after the deletions is structured as follows:

After deleting 20:10 -> 30 -> 40 -> (back to 10) The output will display: 10 30 40
After deleting 10:30 -> 40 -> (back to 30) The output will display: 30 40

Conclusion

A C++ program to implement a circular linked list involves defining the node structure and implementing various operations such as insertion, deletion, and traversal. This article provided a detailed implementation of these operations along with multiple examples to illustrate their functionality. Circular linked lists offer unique advantages for specific applications, making them a valuable tool in a programmer’s toolkit