## 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.

```
#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:

```
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.

```
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:

```
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.

```
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