circularLinkedList.cpp

//circular linked list
#include <bits/stdc++.h>
using namespace std;

typedef struct node
{
    int data;
    node *next = NULL;
} node;

// Function prototypes
void mainMenu();
node *lastNode(node *head);
node *traverse(node *head);
node *insertAtHead(node *head, int val);
node *insertBefore(node *head, int key, int val);
node *insertAfter(node *head, int key, int val);
node *insertAtTail(node *head, int val);
node *deleteAtHead(node *head);
node *deleteBefore(node *head, int key);
node *deleteAfter(node *head, int key);
void deleteTail(node *head);
node *reverseLL(node *head);

void mainMenu()
{
    cout << "\n==================MAIN MENU==================" << endl;
    cout << "1. Insert At head" << endl;
    cout << "2. Insert before value" << endl;
    cout << "3. Insert after value" << endl;
    cout << "4. Insert at tail" << endl;
    cout << "5. Delete At head" << endl;
    cout << "6. Delete before value" << endl;
    cout << "7. Delete after value" << endl;
    cout << "8. Delete at tail" << endl;
    cout << "9. Traverse the circular link list" << endl;
    cout << "10. Reverse the circular link List" << endl;
    cout << "11. Exit" << endl;
}

node *lastNode(node *head)
{
    node *temp = head;
    if (head == NULL)
        return head;
    do
        temp = temp->next;
    while (temp->next != head);
    return temp;
}
node *traverse(node *head)
{
    node *temp = head;

    if (head == NULL)
    {
        cout << "Empty linked list";
        return head;
    }
    do
    {
        cout << temp->data << " -> ";
        temp = temp->next;
    } while (temp != head);
    
    cout << "(head)";
    return temp;
}

node *insertAtHead(node *head, int val)
{
    node *ptr = new node();
    ptr->data = val;
    if (head == NULL)
    {
        ptr->next = ptr;
        head = ptr;
        return head;
    }
    node *lastPtr = lastNode(head);
    ptr->next = head;
    lastPtr->next = ptr;
    head = ptr;
    return head;
}
node *insertBefore(node *head, int key, int val)
{
    if (head == NULL)
    {
        cout << "Linked list is empty so key doesn't exist";
        return head;
    }
    node *temp = head;
    node *nodePtr = new node();
    nodePtr->data = val;
    if (head->data == key)
    {
        head = insertAtHead(head, val);
        return head;
    }
    while (temp->next != head && temp->next->data != key)
        temp = temp->next;
    if (temp->next == head && temp->data != key)
    {
        cout << "Key doesn't exist";
        return head;
    }

    nodePtr->next = temp->next;
    temp->next = nodePtr;
    return head;
}
node *insertAfter(node *head, int key, int val)
{
    if (head == NULL)
    {
        cout << "Linked list is empty so key doesn't exist";
        return head;
    }
    node *temp = head;
    node *nodePtr = new node();
    nodePtr->data = val;

    while (temp->next != head && temp->data != key)
        temp = temp->next;
    if (temp->next == head)
    {
        if (temp->data != key)
        {

            cout << "Key doesn't exist";
            return head;
        }
        insertAtTail(head, val);
        return head;
    }
    nodePtr->next = temp->next;
    temp->next = nodePtr;
    return head;
}
node *insertAtTail(node *head, int val)
{
    node *ptr = new node();
    if (head == NULL)
    {
        return insertAtHead(head, val);
    }
    else
    {
        node *lastPtr = lastNode(head);
        ptr->data = val;
        lastPtr->next = ptr;
        ptr->next = head;
    }
    return head;
}

node *deleteAtHead(node *head)
{
    if (head->next == head)
    {
        delete (head);
        head = NULL;
        return head;
    }
    node *temp = head->next;
    node *lastPtr = lastNode(head);
    delete (head);
    head = temp;
    lastPtr->next = head;
    return head;
}

node *deleteBefore(node *head, int key)
{
    if (head == NULL)
    {
        cout << "Can't delete as linked list is empty";
        return head;
    }
    if (head->data == key)
    {
        deleteTail(head);
        return head;
    }
    if (head->next->data == key)
    {
        head = deleteAtHead(head);
        return head;
    }
    node *currentNodePtr = head;
    node *prevNodePtr = NULL;
    while (currentNodePtr->next != head && currentNodePtr->next->data != key)
    {
        prevNodePtr = currentNodePtr;
        currentNodePtr = currentNodePtr->next;
    }
    if (currentNodePtr->next == head)
    {
        if (currentNodePtr->data != key)
            cout << "Key doesn't exist";
        else
            deleteTail(head);
        return head;
    }
    prevNodePtr->next = currentNodePtr->next;
    delete (currentNodePtr);
    return head;
}

node *deleteAfter(node *head, int key)
{
    if (head == NULL)
    {
        cout << "Can't delete as linked list is empty";
        return head;
    }
    node *temp = head;
    while (temp->next != head && temp->data != key)
        temp = temp->next;
    if (temp->next == head)
    {
        if (temp->data != key)
            cout << "Key doesn't exist";
        else
            head = deleteAtHead(head);
        return head;
    }
    node *temp2 = temp;
    temp->next = temp->next->next;
    delete (temp2->next);

    return head;
}

void deleteTail(node *head)
{
    if (head == NULL)
    {
        cout << "Linked List doesn't exists.";
        return;
    }
    if (head->next == head)
        head = deleteAtHead(head);
    node *temp = head;
    while (temp->next->next != head)
        temp = temp->next;
    delete (temp->next);
    temp->next = head;
}

node *reverseLL(node *head)
{
    if (head == NULL)
    {
        cout << "Can't do the reverse as linked list is empty";
        return head;
    }

    if (head->next == head)
        return head;
    node *prevNode = NULL;
    node *currentNode = head;
    node *nextNode = NULL;

    do
    {
        nextNode = currentNode->next;
        currentNode->next = prevNode;
        prevNode = currentNode;
        currentNode = nextNode;
    } while (currentNode != head);
    head->next = prevNode;
    head = prevNode;
    return head;
}
int main()
{
    node *head = NULL;
    int startLinkSize = 0;
    cout << "Enter the starting linked List size :";
    cin >> startLinkSize;
    cout << "Enter the element with space or enter in between them :";
    int temp;
    while (startLinkSize != 0)
    {
        cin >> temp;
        head = insertAtTail(head, temp);

        startLinkSize--;
    }
    int switchCase = 0;
    int in;

    while (switchCase != 11)
    {
        mainMenu();
        cin >> switchCase;
        switch (switchCase)
        {
        case 1:
            cout << "Enter the data value" << endl;
            cin >> in;
            cout << endl;
            head = insertAtHead(head, in);
            traverse(head);
            break;
        case 2:
        {
            int key;
            cout << "Enter the data value before which you want to add new node" << endl;
            cin >> key;
            cout << "Enter the data value" << endl;
            cin >> in;
            cout << endl;
            head = insertBefore(head, key, in);
            traverse(head);
            break;
        }
        case 3:
        {
            int key;
            cout << "Enter the data value after which you want to add new node" << endl;
            cin >> key;
            cout << "Enter the data value" << endl;
            cin >> in;
            cout << endl;
            head = insertAfter(head, key, in);
            traverse(head);
            break;
        }
        case 4:

            cout << "Enter the data value" << endl;
            cin >> in;
            cout << endl;
            head = insertAtTail(head, in);
            traverse(head);
            break;
        case 5:
            head = deleteAtHead(head);
            traverse(head);
            break;
        case 6:
            cout << "Enter the data value before which node will be deleted" << endl;
            cin >> in;
            cout << endl;
            head = deleteBefore(head, in);
            traverse(head);
            break;
        case 7:
            cout << "Enter the data value after which node will be deleted" << endl;
            cin >> in;
            cout << endl;
            head = deleteAfter(head, in);
            traverse(head);
            break;
        case 8:
            deleteTail(head);
            traverse(head);
            break;
        case 9:
            traverse(head);
            break;
        case 10:
            head = reverseLL(head);
            traverse(head);
            break;
        case 11:
            switchCase = 11;
            break;
        default:
            break;
        }
    }
    return 0;
}