How to insert a node in a Circular Linked List? C++

#cpp #algorithms #datastructures #programming

A Circular Linked List is a variation of Linked List where the first and the last node are also linked to each other, forming a circle. In an ordinary Linked List, the next pointer of the last node points to NULL but in the case of a Circular Linked List, the next pointer of the last node points to the head of the list.

The Circular Linked List makes the traversal in the list more efficient as any node can act as a starting node and the whole list can be traversed starting from any node. It also makes performing operations like enqueue and dequeue easier as the last node and the head node are connected.

Insertion at the head of a Circular Linked List

#include <bits/stdc++.h>
using namespace std;
// Linked List Node
class Node {

public:
    int data;
    Node* next;
    // Constructor
    Node(int info)
    {
        data = info;
        next = NULL;
    }
};
// Inserts at the head of the list
void insertAtFront(Node*& head, int info)
{
    Node* newnode = new Node(info); // Create a new node

    if (head
        == NULL) // if the list has not been created yet
    {
        newnode->next = newnode;
        head = newnode;
        return;
    }
    Node* temp = head; // Creating a pointer for traversal

    while (temp->next != head) //traversing until the first node is encountered again
    {
        temp = temp->next;
    }
    temp->next = newnode;
    newnode->next = head;
    head = newnode;
}

Insertion at the end of the List

#include <bits/stdc++.h>
using namespace std;
// Linked List Node
class Node {

public:
    int data;
    Node* next;
    // Constructor
    Node(int info)
    {
        data = info;
        next = NULL;
    }
};

// Inserts at the tail of the list
void insertAtEnd(Node*& head, int info)
{

    if (head == NULL) {
        insertAtFront(head, info);
        return;
    }

    Node* newnode = new Node(info);
    Node* temp = head; //Creating a pointer for traversal

    while (temp->next != head) //traversing until the first node is encountered again
    {
        temp = temp->next;
    }

    temp->next = newnode;
    newnode->next = head;
}

Insertion in the middle of the Circular List follows the same approach as it would in an ordinary Linked List. You can check it out here.

Following is a complete program that uses both of the above methods of insertion in a Circular linked list and displaying it.

#include <bits/stdc++.h>
using namespace std;
// Linked List Node
class Node {

public:
    int data;
    Node* next;
    // Constructor
    Node(int info)
    {
        data = info;
        next = NULL;
    }
};
// Inserts at the head of the list
void insertAtFront(Node*& head, int info)
{
    Node* newnode = new Node(info);

    if (head == NULL) {
        newnode->next = newnode;
        head = newnode;
        return;
    }
    Node* temp = head;

    while (temp->next != head) {
        temp = temp->next;
    }
    temp->next = newnode;
    newnode->next = head;
    head = newnode;
}
// Inserts at the tail of the list
void insertAtEnd(Node*& head, int info)
{

    if (head == NULL) {
        insertAtFront(head, info);
        return;
    }

    Node* newnode = new Node(info);
    Node* temp = head;

    while (temp->next != head) {
        temp = temp->next;
    }

    temp->next = newnode;
    newnode->next = head;
}

void displaylist(Node* head)
{

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

int main()
{
    Node* head = NULL;
    insertAtEnd(head, 1);
    insertAtEnd(head, 2);
    insertAtEnd(head, 3);
    insertAtEnd(head, 4);
    insertAtFront(head, 5);
    insertAtFront(head, 6);
    displaylist(head); 
}