Circular Linked List (With Source Code)

Circular Linked List

A circular linked list is a data structure that consists of a collection of nodes that are linked together in a circle. Each node in the list contains a data value and a pointer to the next node in the list. The last node in the list points back to the first node, creating a circular loop.

Circular linked lists are a type of linked list that are often used to implement queues and stacks. They are also used to implement linked lists, which are data structures that store elements in a linear order.

Circular Linked List-Simple and Easy Code

Figure: Circular Linked List

Implementation of Circular Linked List

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* next;
};

Node* head = nullptr;

void create(int n) {
    Node* newNode = new Node(); // Create a new node dynamically
    newNode->data = n; // Set the data of the new node to the input value 'n'
    newNode->next = nullptr; // Set the 'next' pointer of the new node to nullptr

    if (head == nullptr) { // If the list is empty
        head = newNode; // Assign the new node as the head
        newNode->next = head; // Make the new node circular by pointing its 'next' to itself
    } else {
        Node* temp = head; // Create a temporary pointer and set it to the head
        while (temp->next != head) { // Traverse the list until the last node is reached
            temp = temp->next; // Move to the next node
        }
        temp->next = newNode; // Assign the new node as the 'next' node of the last node
        newNode->next = head; // Make the new node circular by pointing its 'next' to the head
    }
}

void display() {
    Node* temp = head; // Start from the head
    do {
        cout << temp->data << " "; // Print the data of the current node
        temp = temp->next; // Move to the next node
    } while (temp != head); // Continue until we reach the head again
    cout << endl;
}

int main() {
    int numNodes;
    cout << "Enter the number of nodes: ";
    cin >> numNodes;

    cout << "Enter the data for each node: " << endl;
    for (int i = 0; i < numNodes; i++) {
        int data;
        cin >> data;
        create(data); // Create a new node with the entered data
    }

    cout << "The circular linked list is: ";
    display(); // Display the circular linked list

    return 0;
}

Output:


Enter the number of nodes: 3
Enter the data for each node: 
1 2 4
The circular linked list is: 1 2 4

Insert at any position:

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* next;
};

Node* head = nullptr;

void create(int n) {
    Node* newNode = new Node(); // Create a new node dynamically
    newNode->data = n; // Set the data of the new node to the input value 'n'
    newNode->next = nullptr; // Set the 'next' pointer of the new node to nullptr

    if (head == nullptr) { // If the list is empty
        head = newNode; // Assign the new node as the head
        newNode->next = head; // Make the new node circular by pointing its 'next' to itself
    } else {
        Node* temp = head; // Create a temporary pointer and set it to the head
        while (temp->next != head) { // Traverse the list until the last node is reached
            temp = temp->next; // Move to the next node
        }
        temp->next = newNode; // Assign the new node as the 'next' node of the last node
        newNode->next = head; // Make the new node circular by pointing its 'next' to the head
    }
}

void display() {
    Node* temp = head; // Start from the head
    do {
        cout << temp->data << " "; // Print the data of the current node
        temp = temp->next; // Move to the next node
    } while (temp != head); // Continue until we reach the head again
    cout << endl;
}

void insertAtPosition(int value, int position) {
    if (position <= 0) {
        cout << "Invalid position!" << endl;
        return;
    }

    Node* newNode = new Node(); // Create a new node dynamically
    newNode->data = value; // Set the data of the new node to the input value 'value'
    newNode->next = nullptr;

    if (head == nullptr) { // If the list is empty
        head = newNode; // Assign the new node as the head
        newNode->next = head; // Make the new node circular by pointing its 'next' to itself
        return;
    }

    if (position == 1) { // If the position is 1, insert at the beginning
        newNode->next = head; // Set the 'next' pointer of the new node to the current head
        Node* temp = head; // Create a temporary pointer and set it to the head
        while (temp->next != head) { // Traverse to the last node
            temp = temp->next;
        }
        temp->next = newNode; // Assign the new node as the 'next' node of the last node
        head = newNode; // Update the head to the new node
    } else {
        Node* temp = head; // Create a temporary pointer and set it to the head
        int currentPosition = 1;
        while (currentPosition < position - 1 && temp->next != head) { // Traverse to the node at position - 1
            temp = temp->next;
            currentPosition++;
        }
        if (currentPosition != position - 1) { // If the position is out of range
            cout << "Invalid position!" << endl;
            delete newNode; // Delete the dynamically created node
            return;
        }
        newNode->next = temp->next; // Set the 'next' pointer of the new node to the next node of temp
        temp->next = newNode; // Set the 'next' pointer of temp to the new node
    }
}

int main() {
    int numNodes;
    cout << "Enter the number of nodes: ";
    cin >> numNodes;

    cout << "Enter the data for each node: " << endl;
    for (int i = 0; i < numNodes; i++) {
        int data;
        cin >> data;
        create(data); // Create a new node with the entered data
    }

    cout << "The circular linked list is: ";
    display(); // Display the circular linked list

    int value, position;
    cout << "Enter the value to insert: ";
    cin >> value;
    cout << "Enter the position to insert: ";
    cin >> position;

    insertAtPosition(value, position); // Insert the node at the specified position

    cout << "The updated circular linked list is: ";
    display(); // Display the updated circular linked list

    return 0;
}

Output:

Enter the number of nodes: 3
Enter the data for each node: 
1 2 3
The circular linked list is: 1 2 3 
Enter the value to insert: 5
Enter the position to insert: 4
The updated circular linked list is: 1 2 3 5

Deletion at any position:

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node* next;
};

Node* head = nullptr;

// Function to create a circular linked list
void create(int n) {
    Node* newNode = new Node(); // Create a new node dynamically
    newNode->data = n; // Set the data of the new node to the input value 'n'

    if (head == nullptr) { // If the list is empty
        head = newNode; // Assign the new node as the head
        newNode->next = head; // Make the new node circular by pointing its 'next' to itself
    } else {
        Node* temp = head; // Create a temporary pointer and set it to the head
        while (temp->next != head) { // Traverse the list until the last node is reached
            temp = temp->next; // Move to the next node
        }
        temp->next = newNode; // Assign the new node as the 'next' node of the last node
        newNode->next = head; // Make the new node circular by pointing its 'next' to the head
    }
}

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

    Node* temp = head; // Start from the head
    do {
        cout << temp->data << " "; // Print the data of the current node
        temp = temp->next; // Move to the next node
    } while (temp != head); // Continue until we reach the head again
    cout << endl;
}

// Function to delete a node at a specific position in the circular linked list
void deleteNode(int position) {
    if (head == nullptr) { // If the list is empty
        cout << "Circular linked list is empty. Cannot delete node." << endl;
        return;
    }

    Node* currentNode = head; // Start from the head
    Node* previousNode = nullptr;
    int count = 1;

    while (currentNode->next != head && count != position) { // Traverse to the node at the specified position
        previousNode = currentNode;
        currentNode = currentNode->next;
        count++;
    }

    if (count != position) { // If the position is out of range
        cout << "Invalid position. Node does not exist at position " << position << endl;
        return;
    }

    if (currentNode == head) { // If the node to be deleted is the head
        // Move to the last node to update the 'next' pointer
        Node* lastNode = head;
        while (lastNode->next != head) {
            lastNode = lastNode->next;
        }

        if (head == head->next) { // If there is only one node in the circular linked list
            head = nullptr;
        } else {
            head = head->next; // Move the head to the next node
            lastNode->next = head; // Update the 'next' pointer of the last node
        }
    } else {
        previousNode->next = currentNode->next; // Update the 'next' pointer of the previous node
    }

    delete currentNode; // Free the memory occupied by the deleted node
    cout << "Node at position " << position << " has been deleted." << endl;
}

int main() {
    int numNodes;
    cout << "Enter the number of nodes: ";
    cin >> numNodes;

    cout << "Enter the data for each node: " << endl;
    for (int i = 0; i < numNodes; i++) {
        int data;
        cin >> data;
        create(data); // Create a new node with the entered data
    }

    cout << "The circular linked list is: ";
    display(); // Display the circular linked list

    int position;
    cout << "Enter the position of the node to delete: ";
    cin >> position;

    deleteNode(position); // Delete the node at the specified position

    cout << "The updated circular linked list is: ";
    display(); // Display the updated circular linked list

    return 0;
}

Output:


Enter the number of nodes: 3
Enter the data for each node: 
1 2 3 
The circular linked list is: 1 2 3 
Enter the position of the node to delete: 3
Node at position 3 has been deleted.
The updated circular linked list is: 1 2

Advantages of Circular Linked Lists

Circular linked lists are efficient for operations that involve traversing the list in both directions, such as searching and inserting elements.
Circular linked lists are also efficient for operations that involve deleting elements from the middle of the list, as there is no need to update the pointers of the elements that follow the deleted element.

Disadvantages of Circular Linked Lists

Circular linked lists are not as efficient for operations that involve inserting or deleting elements at the beginning or end of the list, as all of the pointers in the list need to be updated.
Circular linked lists can be more difficult to implement than other types of linked lists.

Circular linked lists are a data structure that can be used to implement a variety of data structures, such as queues, stacks, and linked lists. They are efficient for operations that involve traversing the list in both directions, and they are also efficient for operations that involve deleting elements from the middle of the list. However, they are not as efficient for operations that involve inserting or deleting elements at the beginning or end of the list.

EduCodiv

Circular Linked List (With Source Code)