12. DSA with C++ - Circular Linked List

Circular Linked List

A circular linked list is a variation of a linked list in which the last node points back to the first node, forming a circular structure. It provides the ability to traverse the list in a continuous loop. Here's an explanation of circular linked lists and an example implementation in C++.

Circular Linked List Explanation:

In a circular linked list, each node contains a data element and a pointer to the next node. The last node's pointer points back to the first node, creating a circular structure. This allows traversal from any node to any other node in the list.

Key Operations on Circular Linked List:

1. Insertion: Insert a new node at the beginning, end, or any desired position in the circular linked list.
2. Deletion: Remove a node from the circular linked list based on its position or data value.
3. Traversal: Traverse the circular linked list, starting from any node, and visit each node in the list.
4. Searching: Search for a specific element in the circular linked list.
5. Display: Print the data elements of the circular linked list.

Now, let's go through the step-by-step implementation of circular linked lists in C++ with example code:

#include <iostream>

// Node structure for circular linked list
struct Node {
    int data;
    Node* next;
};

// Function to create a new node
Node* createNode(int value) {
    Node* newNode = new Node;
    newNode->data = value;
    newNode->next = nullptr;
    return newNode;
}

// Function to insert a node at the beginning of the circular linked list
void insertAtBeginning(Node** head, int value) {
    Node* newNode = createNode(value);
    if (*head == nullptr) {
        newNode->next = newNode;
    } else {
        Node* last = (*head)->next;
        while (last->next != *head) {
            last = last->next;
        }
        newNode->next = *head;
        last->next = newNode;
    }
    *head = newNode;
}

// Function to insert a node at the end of the circular linked list
void insertAtEnd(Node** head, int value) {
    Node* newNode = createNode(value);
    if (*head == nullptr) {
        newNode->next = newNode;
        *head = newNode;
    } else {
        Node* last = (*head)->next;
        while (last->next != *head) {
            last = last->next;
        }
        newNode->next = *head;
        last->next = newNode;
    }
}

// Function to delete a node with a given key from the circular linked list
void deleteNode(Node** head, int key) {
    if (*head == nullptr) {
        return;
    }

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

    if (curr == *head && curr->next == *head) {
        *head = nullptr;
        delete curr;
        return;
    }

    if (curr == *head) {
        prev = *head;
        while (prev->next != *head) {
            prev = prev->next;
        }
        *head = (*head)->next;
        prev->next = *head;
    } else if (curr->next == *head) {
        prev->next = *head;
    } else {
        prev->next = curr->next;
    }

   

 delete curr;
}

// Function to traverse and display the circular linked list
void displayList(Node* head) {
    if (head == nullptr) {
        std::cout << "Circular linked list is empty." << std::endl;
        return;
    }

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

int main() {
    Node* head = nullptr;

    // Insert nodes at the beginning
    insertAtBeginning(&head, 3);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 1);

    // Display the circular linked list
    std::cout << "Circular linked list after inserting at the beginning: ";
    displayList(head);

    // Insert nodes at the end
    insertAtEnd(&head, 4);
    insertAtEnd(&head, 5);

    // Display the circular linked list
    std::cout << "Circular linked list after inserting at the end: ";
    displayList(head);

    // Delete a node from the circular linked list
    deleteNode(&head, 2);

    // Display the circular linked list after deletion
    std::cout << "Circular linked list after deleting a node: ";
    displayList(head);

    return 0;
}

In this example, we create a circular linked list with nodes containing integer values. Let's go through the step-by-step implementation:

1. Define the Node structure for the circular linked list, which consists of a data element and a pointer to the next node.
2. Implement the createNode function to create a new node with a given value.
3. Implement the insertAtBeginning function to insert a new node at the beginning of the circular linked list. If the list is empty, the new node points to itself. Otherwise, the new node is inserted before the head node, and the last node's pointer is updated.
4. Implement the insertAtEnd function to insert a new node at the end of the circular linked list. If the list is empty, the new node points to itself and becomes the head. Otherwise, the new node is inserted after the last node, and the last node's pointer is updated.
5. Implement the deleteNode function to delete a node with a given key from the circular linked list. It handles various cases, including deleting the head node, the last node, and any node in between.
6. Implement the displayList function to traverse and display the circular linked list. It starts from the head node and continues until it reaches the head again, printing the data elements of each node.
7. In the main function, we create a circular linked list and perform various operations:
   • Insert three nodes at the beginning.
   • Display the list.
   • Insert two nodes at the end.
   • Display the list.
   • Delete a node with a specific key.
   • Display the list after deletion.

When you run the code, the output will be:

Circular linked list after inserting at the beginning: 1 2 3
Circular linked list after inserting at the end: 1 2 3 4 5
Circular linked list after deleting a node: 1 3 4 5

This example demonstrates the step-by-step implementation of a circular linked list in C++, including inserting nodes at the beginning and end, deleting a node, and displaying the list.