Circular Linked List Insertion in the middle in C++

February 21, 2023

Program in C++ for Circular Linked List insertion in the middle

On this blog we will explore different codes to do Insertion in a Circular Linked List in the middle in C++
circular Node
  • Method 1: Using additional size variable
  • Method 2: Using an additional function to calculate the size
Circular Linked List Insertion in the middle in C++
DSA desktop gif
DSA mobile gif

Circular Linked List in C++

Insertion in Circular Linked List

Insertion at the beginning in circular linked list 

Deletion from beginning in Circular Linked List

Deletion from nth position in Circular Linked List

Run 
#include<iostream>
using namespace std;

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

int size = 0;
void insert(Node** head, int data){
    
    Node* newNode = new Node();
    newNode->data = data;
    
    // if its the first node being entered
    if(*head == NULL){
        *head = newNode;
        (*head)->next = *head;
        size++;
        return;
    }
    
    // if Circular Linked List had >=1 node
    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;
    
    size++;
}
void insertMiddle(Node** head, int data){
    
    Node* newNode = new Node();
    newNode->data = data;
    
    // if the LL was empty
    if(*head == NULL){
        // use insert function to insert
        insert(head, data);
        return;
    }
    
    // otherwise
    Node* temp = *head;
    
    // find correct insertion position for middle
    int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;
    
    // Unique case when there is only one node in CLL
    // we will be inserting at the last, 
    // inserting 2nd node at the last
    // Example size = 1 will result in mid = 1 so entering after 1st node
    // where size itself is 1 so entering last node
    if(mid == size){
        newNode->next = *head;
        (*head)->next = newNode;
        size++;
        return;
    }
    // traverse to current mid position
    while(--mid){
        temp = temp->next;
    }
    
    newNode->next = temp->next;
    temp->next = newNode;
    size++;
}

void display(Node* head){
    // if there are no node in LL
    if(head == NULL)
        return;
    cout << "Linked List: ";
    Node* temp = head;
    
    //need to take care of circular structure of LL
    do{
        cout <<temp->data << " "; 
        temp = temp->next;
        
    }while(temp!=head);
    cout << "\n" << endl;
}

int main()
{
    Node* head = NULL;

    insert(&head,20);
    insert(&head,4);

    display(head); 

    insertMiddle(&head, 8);
    display(head); 

    insertMiddle(&head, 16);
    display(head); 
    
    insertMiddle(&head, 12);
    display(head); 

    return 0; 
}

Output

Linked List: 4 20 

Linked List: 4 8 20 

Linked List: 4 8 16 20 

Linked List: 4 8 12 16 20
Run 
#include<iostream>
using namespace std;

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

int getSize(Node* node);

void insert(Node** head, int data){
    
    Node* newNode = new Node();
    newNode->data = data;
    
    // if its the first node being entered
    if(*head == NULL){
        *head = newNode;
        (*head)->next = *head;
        return;
    }
    
    // if Circular Linked List had >=1 node
    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;
    
}
void insertMiddle(Node** head, int data){
    
    Node* newNode = new Node();
    newNode->data = data;
    
    // if the LL was empty
    if(*head == NULL){
        // use insert function to insert
        insert(head, data);
        return;
    }
    
    // otherwise
    Node* temp = *head;
    int size = getSize(*head);
    
    
    // find correct insertion position for middle
    int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;
    
    // Unique case when there is only one node in CLL
    // we will be inserting at the last, 
    // inserting 2nd node at the last
    // Example size = 1 will result in mid = 1 so entering after 1st node
    // where size itself is 1 so entering last node
    if(mid == size){
        newNode->next = *head;
        (*head)->next = newNode;
        return;
    }
    // traverse to current mid position
    while(--mid){
        temp = temp->next;
    }
    
    newNode->next = temp->next;
    temp->next = newNode;
}

int getSize(Node* head){
    int size = 0;
    
    Node* node = head;
    do{
        node = node->next;
        size++;
        
    }while(node!=head);

    return size;
}
void display(Node* head){
    // if there are no node in LL
    if(head == NULL)
        return;
    cout << "Linked List: ";
    Node* temp = head;
    
    //need to take care of circular structure of LL
    do{
        cout << temp->data << " "; temp = temp->next;
        
    }while(temp!=head);
    cout << "\n" << endl;
}

int main()
{
    Node* head = NULL;

    insert(&head,20);
    insert(&head,4);

    display(head); 

    insertMiddle(&head, 8);
    display(head); 

    insertMiddle(&head, 16);
    display(head); 
    
    insertMiddle(&head, 12);
    display(head); 

    return 0; 
}

Output

Linked List: 4 20 

Linked List: 4 8 20 

Linked List: 4 8 16 20 

Linked List: 4 8 12 16 20

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

Circular Linked List

  • Introduction to Circular Linked List
    Click Here
  • Circular Linked List Applications
    Click Here
  • Circular Linked List in –
    C | C++ | Java
  • 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 –
  • Deletion from end in Circular Linked List –
    C | C++ | Java
  • Insertion and Deletion in Circular Linked List – C | C++ | Java
  • Split a Circular Linked List in two halves –
    C | C++ | Java
  • Count nodes in Circular Linked List –
    C | C++ | Java
  • Sorted Insert In Circular Linked List –
    C | C++ | Java
  • Insertion in the middle in Circular Linked List –
    C | C++ | Java

Circular Linked List