//NAME: RAO SUBHAN ATHAR
//SEC:A
//ROLL NO. :335
//Submitted to : Muzahir Saleem
// Lab-16 = Implement Circular Queue and its operations.

#include<iostream>
using namespace std;

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

    // Constructor to initialize a node with given data and null link
    Node(int value) : data(value), next(nullptr) {}
};

// Circular Linked List class
class CircularLinkedList {
public:
    Node* head;

    // Constructor to initialize head to null
    CircularLinkedList() : head(nullptr) {}

    // Function to insert at the front of the circular linked list
    void insertFront(int value) {
        Node* newNode = new Node(value);

        if (head == nullptr) {
            head = newNode;
            newNode->next = head;
        } else {
            Node* temp = head;
            while (temp->next != head) {
                temp = temp->next;
            }
            temp->next = newNode;
            newNode->next = head;
            head = newNode;
        }
    }

    // Function to delete a node with a given value
    void deleteNode(int value) {
        if (head == nullptr) {
            cout << "List is empty. Cannot delete from an empty list." << endl;
            return;
        }

        Node* temp = head;
        Node* prev = nullptr;

        do {
            if (temp->data == value) {
                if (temp == head) {
                    if (temp->next == head) {
                        delete temp;
                        head = nullptr;
                        return;
                    } else {
                        Node* last = head;
                        while (last->next != head) {
                            last = last->next;
                        }
                        last->next = head->next;
                        delete head;
                        head = last->next;
                    }
                } else {
                    prev->next = temp->next;
                    delete temp;
                }
                cout << "Node with value " << value << " deleted." << endl;
                return;
            }

            prev = temp;
            temp = temp->next;
        } while (temp != head);

        cout << "Node with value " << value << " not found." << endl;
    }

    // Function to display the circular linked list
    void displayList() {
        if (head == nullptr) {
            cout << "List is empty." << endl;
            return;
        }

        Node* temp = head;
        do {
            cout << temp->data << " ";
            temp = temp->next;
        } while (temp != head);

        cout << endl;
    }
};

// Main program
int main() {
    // Create a circular linked list
    CircularLinkedList* cll = new CircularLinkedList;

    // Insert elements at the front of the circular linked list
    cll->insertFront(3);
    cll->insertFront(2);
    cll->insertFront(1);

    cout << "Circular Linked List elements after insertion at front: ";
    // Display elements in Circular Linked List
    cll->displayList();

    // Delete a node from the circular linked list
    cll->deleteNode(2);

    cout << "Circular Linked List elements after deletion: ";
    // Display elements in Circular Linked List after deletion
    cll->displayList();

    return 0;
}