by Jasleen Chhabra | Updated on 24 August 2024

A circular linked list is a variation of the linked list where the last node points back to the first node, creating a circular structure. This configuration is useful in applications where the entire list needs to be looped through continuously, such as in round-robin scheduling or buffering systems.

Key Operations on Circular Linked Lists

1. Insertion
2. Deletion
3. Traversal
4. Searching

Insertion: Adding a New Node to the Circular Linked List

Insertion in a circular linked list can occur at the beginning, end, or any specific position within the list.

At the Beginning

Algorithm:

1. Create a new node.
2. Set the new node’s next pointer to the current head.
3. Traverse to the last node.
4. Set the last node’s next pointer to the new node.
5. Update the head to the new node.

C++ Implementation:

struct Node {

    int data;

    Node* next;

};

 

void insertAtBeginning(Node*& head, int newData) {

    Node* newNode = new Node();

    newNode->data = newData;

    newNode->next = head;

 

    if (head == nullptr) {

        newNode->next = newNode;

        head = newNode;

        return;

    }

 

    Node* temp = head;

    while (temp->next != head) {

        temp = temp->next;

    }

    temp->next = newNode;

    head = newNode;

}

At the End

Algorithm:

1. Create a new node.
2. Traverse to the last node.
3. Set the new node’s next pointer to the head.
4. Set the last node’s next pointer to the new node.

C++ Implementation:

void insertAtEnd(Node*& head, int newData) {

    Node* newNode = new Node();

    newNode->data = newData;

 

    if (head == nullptr) {

        newNode->next = newNode;

        head = newNode;

        return;

    }

 

    Node* temp = head;

    while (temp->next != head) {

        temp = temp->next;

    }

    temp->next = newNode;

    newNode->next = head;

}

---

Deletion: Removing an Existing Node from the Circular Linked List

Deletion involves removing a node and adjusting the pointers accordingly.

First Node

Algorithm:

1. Traverse to the last node.
2. Update the head to the next node.
3. Set the last node’s next pointer to the new head.
4. Delete the original head node.

C++ Implementation:

void deleteFirstNode(Node*& head) {

    if (head == nullptr) return;

 

    if (head->next == head) {

        delete head;

        head = nullptr;

        return;

    }

 

    Node* temp = head;

    while (temp->next != head) {

        temp = temp->next;

    }

 

    Node* toDelete = head;

    temp->next = head->next;

    head = head->next;

    delete toDelete;

}

Specific Node

Algorithm:

1. Traverse to the node before the target node.
2. Update the previous node’s next pointer to skip the target node.
3. Delete the target node.

C++ Implementation:

void deleteNode(Node*& head, int key) {

    if (head == nullptr) return;

 

    if (head->data == key && head->next == head) {

        delete head;

        head = nullptr;

        return;

    }

 

    Node* temp = head;

    Node* prev = nullptr;

    while (temp->data != key) {

        prev = temp;

        temp = temp->next;

    }

 

    if (temp->next == head) {

        prev->next = head;

        delete temp;

        return;

    }

 

    prev->next = temp->next;

    delete temp;

}

---

Last Node

Algorithm:

1. Traverse to the second-to-last node.
2. Set the second-to-last node’s next pointer to the head.
3. Delete the last node.

C++ Implementation:

void deleteLastNode(Node*& head) {

    if (head == nullptr) return;

 

    if (head->next == head) {

        delete head;

        head = nullptr;

        return;

    }

 

    Node* temp = head;

    Node* prev = nullptr;

    while (temp->next != head) {

        prev = temp;

        temp = temp->next;

    }

 

    prev->next = head;

    delete temp;

}

---

Traversal: Accessing Each Node in the Circular Linked List

Traversal involves accessing each node in a sequential manner, starting from the head and moving back to the head after the last node.

Algorithm:

1. Start from the head.
2. Access each node and move to the next until the head is reached again.

C++ Implementation:

void traverseList(Node* head) {

    if (head == nullptr) return;

 

    Node* temp = head;

    do {

        std::cout << temp->data << " ";

        temp = temp->next;

    } while (temp != head);

    std::cout << std::endl;

}

---

Searching: Finding a Node with a Specific Value

Searching involves finding a node that contains a specific value.

Algorithm:

1. Start from the head.
2. Compare each node’s data with the target value.
3. If found, return the node; otherwise, continue until the head is reached again.

C++ Implementation:

Node* search(Node* head, int key) {

    if (head == nullptr) return nullptr;

 

    Node* temp = head;

    do {

        if (temp->data == key) {

            return temp;

        }

        temp = temp->next;

    } while (temp != head);

    return nullptr;

}

This blog content provides an in-depth look at circular linked lists, covering key operations such as insertion, deletion, traversal, and searching, along with their algorithms and C++ implementations.

---