Circular Linked List Implementation in CPP

1. Introduction

A Circular Linked List is a variation of the linked list in which the last node points back to the first node, forming a closed loop. This structure allows for continuous traversal, moving from the last node to the first node seamlessly. In this blog post, we'll delve into the basic implementation of a circular linked list in C++.

2. Implementation Steps

1. Declare a Node class to represent individual elements in the list. This class will have two members: data and a next pointer.

2. Declare a CircularLinkedList class that will encapsulate the behavior of the circular list.

3. Define methods to add an item at the end (append), add an item at the beginning (prepend), remove an item (remove), and display the list (display).

4. Demonstrate the usage of the CircularLinkedList class.

3. Implementation in C++ Programming

#include<iostream>
class Node {
public:
    int data;           // Data to be stored
    Node* next;         // Pointer to the next node
    Node(int value) {
        data = value;
        next = nullptr;
    }
};

class CircularLinkedList {
private:
    Node* head;
public:
    CircularLinkedList() {
        head = nullptr;
    }
    
    void append(int value) {
        Node* newNode = new Node(value);
        if (head == nullptr) {
            head = newNode;
            newNode->next = head;
            return;
        }
        Node* temp = head;
        while (temp->next != head) {
            temp = temp->next;
        }
        temp->next = newNode;
        newNode->next = head;
    }
    
    void prepend(int value) {
        Node* newNode = new Node(value);
        Node* temp = head;
        newNode->next = head;
        if (head == nullptr) {
            newNode->next = newNode;
        } else {
            while (temp->next != head) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
        head = newNode;
    }
    
    void display() {
        if (head == nullptr) return;
        Node* temp = head;
        do {
            std::cout << temp->data << " -> ";
            temp = temp->next;
        } while (temp != head);
        std::cout << "head" << std::endl;
    }
    
    void remove(int value) {
        if (head == nullptr) return;
        Node* temp = head;
        Node* prev = nullptr;
        do {
            if (temp->data == value) {
                if (prev != nullptr) {
                    prev->next = temp->next;
                    if (head == temp) {
                        head = head->next;
                    }
                    delete temp;
                    return;
                } else {
                    while (temp->next != head) {
                        temp = temp->next;
                    }
                    temp->next = head->next;
                    delete head;
                    head = temp->next;
                }
            }
            prev = temp;
            temp = temp->next;
        } while (temp != head);
    }
};

int main() {
    CircularLinkedList cll;
    cll.append(10);
    cll.append(20);
    cll.prepend(5);
    std::cout << "Circular Linked List: ";
    cll.display();
    cll.remove(10);
    std::cout << "After removing 10: ";
    cll.display();
    return 0;
}

Output:

Circular Linked List: 5 -> 10 -> 20 -> head
After removing 10: 5 -> 20 -> head

Explanation:

1. The Node class represents individual elements of the circular linked list. Each node contains data and a pointer to the next node.

2. The CircularLinkedList class encapsulates the behavior of the circular list.

3. append(int value): Adds a node with the provided value to the end of the list.

4. prepend(int value): Adds a node with the provided value to the beginning of the list.

5. display(): Traverses and prints each node's data until it reaches the head again.

6. remove(int value): Searches for a node with the given value and removes it from the list, adjusting the pointers of surrounding nodes accordingly.

7. main(): Demonstrates the usage of the circular linked list by adding nodes both at the beginning and the end, and then removing a node.