Insertion at the beginning in Circular Linked List in C++

How to insert new node at beginning in a circular linked list in C++?

On this page we will look at different methods to insert at the start or beginning in a circular linked list

C++ program for insertion at beginning in circular linked list in C++

What insertion at the beginning may require?

  • Changing the current head
  • Changing the next node of the last node in circular linked list.
Circular Linked List Insertion at the beginning

Methods discussed

  • Method 1: Linked List Insertion using Struct
  • Method 2: Linked List Insertion using class (without class methods)
  • Method 3: Linked List Insertion using class (with class methods)

C++ Program for insertion at beginning in circular linked list

We will look at all the three methods below –

Linked List Insertion using Struct
Run
#include<iostream>
#include<stdio.h>
using namespace std;

// structure for Circular Linked List
struct Node
{
   int data;
   struct Node *next;
};

int calcSize(struct Node* head);

void insertStart(struct Node** head, int data)
{
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    newNode->data = data;
    
    // if its the first node being entered
    if(*head == NULL)
    {
        *head = newNode; // assigning itself as head
        (*head)->next = *head; // assigning itself as next node

        cout << newNode->data << " Inserted\n"; 
        return; 
    } 

    // if CLL already as >=1 node
    struct Node* curr = *head;
    
    // traverse till last node in CLL
    while(curr->next != *head){
        curr = curr->next;
    }
    
    curr->next = newNode; // last node's next as this new node
    newNode->next = *head; // new node's next as current head node

    *head = newNode; // changing head node to this new node
    cout << newNode->data << " Inserted\n";
    
    // previous head node becomes 2nd node
}

void display(struct Node* head){
    // if there are no node in CLL
    if(head == NULL)
        return;
    
    struct Node* temp = head;
    cout << "\nLinked List : ";

    //need to take care of circular structure of CLL
    do{
        cout << temp->data << " "; 
        temp = temp->next;
        
    }while(temp!=head);
    cout << endl;
}

int main(){
    
    // first node will be null at creation    
    struct Node* head = NULL;
    
    insertStart(&head,1);
    insertStart(&head,2);
    insertStart(&head,3);
    insertStart(&head,4);
    insertStart(&head,5);

    display(head);
  
    return 0;
}

Output

1 Inserted
2 Inserted
3 Inserted
4 Inserted
5 Inserted

Linked List : 5 4 3 2 1
Linked List Insertion using class (without class methods)
Run
#include<iostream>
using namespace std;

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


void insertStart(Node** head, int data)
{
    Node* newNode = new Node();
    newNode->data = data;
    
    // if first node is being inserted
    if(*head == NULL){
        *head = newNode; 
        (*head)->next = *head;
        
        cout << newNode->data << " Inserted" << endl; 
        return; 
    } 

    // if had more than 1 node do below 
    Node* curr = *head; 

    // traverse till last node in circular Linked List 
    while(curr->next != *head){
        curr = curr->next;
    }
    
    curr->next = newNode;
    newNode->next = *head;

    cout << newNode->data << " Inserted" << endl;
    *head = newNode;
}

void display(Node* head){
    
    cout << "\nLinked List : " << endl;
    
    // if circular linked list is empty currently
    if(head == NULL)
        return;
    
    Node* temp = head;
    
    // since we need to take care of circular nature of linked list
    do{
        cout << temp->data << " "; 
        temp = temp->next;
        
    }while(temp!=head);
    cout << endl;
}

int main(){
    
    // first node will be null at creation    
    Node* head = NULL;
    
    insertStart(&head,1);
    insertStart(&head,2);
    insertStart(&head,3);
    insertStart(&head,4);
    insertStart(&head,5);
    
    display(head);

  
    return 0;
}

Output

1 Inserted
2 Inserted
3 Inserted
4 Inserted
5 Inserted

Linked List : 
5 4 3 2 1
Since we use internal class function in this method we do not require to pass head everytime, in functions.
Run
#include<iostream>
using namespace std;

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

class LinkedList
{
    private:
        Node* head;
    public:
        LinkedList() { // constructor
        head = NULL;
    }
    void insertStart(int data);
    void display();
};

void LinkedList::insertStart(int data)
{
    Node* newNode = new Node();
    newNode->data = data;
    
    // if first node is being inserted
    if(head == NULL){
        head = newNode;
        head->next = head;
        
        cout << newNode->data << " inserted" << endl; 
        return; 
    } 

    // if had more than 1 node do below 
    Node* curr = head; 

    // traverse till last node in circular Linked List 
    while(curr->next != head){
        curr = curr->next;
    }
    
    curr->next = newNode;
    newNode->next = head;
    
    head = newNode;
    cout << newNode->data << " inserted" << endl;
}

void LinkedList::display(){
    
    cout << "\nCircular Linked List : " << endl;

    // if circular linked list is empty currently
    if(head == NULL)
        return;
    
    Node* temp = head;
    
    // since we need to take care of circular nature of linked list
    do{
        cout << temp->data << " "; 
        temp = temp->next;
        
    }while(temp!=head);
    cout << endl; 
} 

int main() 
{ 

    // first node will be null at creation 
    LinkedList* circular_list = new LinkedList();

    circular_list->insertStart(1);
    circular_list->insertStart(2);
    circular_list->insertStart(3);
    circular_list->insertStart(4);
    circular_list->insertStart(5);
    
    circular_list->display();
    return 0;
}

Output

1 inserted
2 inserted
3 inserted
4 inserted
5 inserted

Circular Linked List : 
5 4 3 2 1

Also check the following pages

  • Insertion in Circular Linked List – C | C++ | Java
    • Insertion at the beginning– C | C++ | Java
    • Insertion at the end – C | C++ | Java
    • Insertion at nth position – C | C++ | Java
  • Deletion in Circular Linked List – C | C++ | Java
    • Deletion from beginning in Circular Linked List – C | C++ | Java
    • Deletion from nth position in Circular Linked List – C++ | Java
    • Deletion from end in Circular Linked List – C | C++ | Java
  • Insertion and Deletion in a Circular Linked List – C | C++ | Java