#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
class CircularLinkedList {
private:
Node* head;
Node* cursor; // Points to the last node
public:
CircularLinkedList() : head(nullptr), cursor(nullptr) {}
~CircularLinkedList() {
if (!isEmpty()) {
Node* current = head;
Node* next;
cursor->next = nullptr; // Break the loop
while (current != nullptr) {
next = current->next;
delete current;
current = next;
}
}
}
bool isEmpty() const {
return head == nullptr;
}
void insertAtBeginning(int data) {
Node* newNode = new Node{data, nullptr};
if (isEmpty()) {
head = cursor = newNode;
newNode->next = head;
} else {
newNode->next = head;
head = newNode;
cursor->next = head;
}
}
void insertAtEnd(int data) {
Node* newNode = new Node{data, nullptr};
if (isEmpty()) {
head = cursor = newNode;
newNode->next = head;
} else {
newNode->next = head;
cursor->next = newNode;
cursor = newNode;
}
}
void deleteFirst() {
if (isEmpty()) {
cout << "List is empty." << endl;
return;
}
if (head == cursor) {
delete head;
head = cursor = nullptr;
} else {
Node* temp = head;
head = head->next;
cursor->next = head;
delete temp;
}
}
void deleteLast() {
if (isEmpty()) {
cout << "List is empty." << endl;
return;
}
if (head == cursor) {
delete cursor;
head = cursor = nullptr;
} else {
Node* current = head;
while (current->next != cursor) {
current = current->next;
}
current->next = head;
delete cursor;
cursor = current;
}
}
void deleteNodeWithValue(int key) {
if (isEmpty()) {
cout << "List is empty." << endl;
return;
}
if (head->data == key) {
deleteFirst();
return;
}
Node* prev = head;
Node* curr = head->next;
while (curr != head && curr->data != key) {
prev = curr;
curr = curr->next;
}
if (curr == head) {
cout << "Value not found." << endl;
return;
}
prev->next = curr->next;
if (curr == cursor) {
cursor = prev;
}
delete curr;
}
bool search(int key) const {
if (isEmpty()) return false;
Node* current = head;
do {
if (current->data == key) return true;
current = current->next;
} while (current != head);
return false;
}
int length() const {
if (isEmpty()) return 0;
int count = 0;
Node* current = head;
do {
count++;
current = current->next;
} while (current != head);
return count;
}
void display() const {
if (isEmpty()) {
cout << "List is empty." << endl;
return;
}
Node* current = head;
do {
cout << current->data << " ";
current = current->next;
} while (current != head);
cout << endl;
}
};
int main() {
CircularLinkedList list;
[Link](1);
[Link](2);
[Link](3);
[Link](4);
cout << "List: ";
[Link]();
[Link]();
cout << "After deleting first: ";
[Link]();
[Link]();
cout << "After deleting last: ";
[Link]();
[Link](10);
[Link](20);
cout << "After more insertions: ";
[Link]();
cout << "Search 20: " << ([Link](20) ? "Found" : "Not Found") << endl;
cout << "Search 5: " << ([Link](5) ? "Found" : "Not Found") << endl;
[Link](2);
cout << "After deleting node with value 2: ";
[Link]();
cout << "Length: " << [Link]() << endl;
return 0;
}