Insertion at specific position in Circular Linked List in C++

Program for insertion at specific position in circular linked list in C++

How we can insert data at specific position in circular linked list?

Insertion at specific position in circular linked list in C++ is one the insertion operation that we can perform on the circular linked list. In this article we will be learning steps and algorithm to do the same. We can perform insertion at following places also:-

  • Insertion at the beginning of the circular linked list.
  • Insertion at the end of the circular linked list.

Steps to insert new node at specific position in circular linked list in CPP

These steps are used in CPP programming for insertion at specific position in circular linked list

  1. If the circular linked list is empty, terminate function.
  2. Else define two node pointers.
  3. Create new node and stor the data in the new node
  4. Now traverse till the specific position and insert this new node there.
  5. Link the pointer of this new node to the node present at this place previously.
  6. Print the new circular linked list to see the result.

Constructing nodes of circular linked list

Syntax

class Node  

    int data; 
    Node *next; 
}; 
Insertion at specific position in circular linked list in C++

Algorithm to write a CPP program to insert at specific position in Circular Linked List

Below is the algorithm for insertion at specific position in circular linked list

  • STRUCT NEWNODE & CURNODE
  • IF HEAD==NULL
  • EXIT
  • ELSE
  • NEWNODE->NUM=NUM
  • CURNODE=HEAD
  • FOR I=0 TO POS-3
  • CURRNODE=CURRNODE->NEXT
  • END FOR
  • NEWNODE->NEXT=CURNODE->NEXT
  • CURNODE->NEXT=NEWNODE

C++ program for insertion at specific position in circular linked list

#include <iostream>
using namespace std;

struct node {
    int num;
    struct node * next;
}*head;

void make(int n)//function to build linked list
{
    int i, num;
    struct node *preptr, *newnode;

    if(n >= 1)
    {
        head = (struct node *)malloc(sizeof(struct node));

        cout<<"Enter data of the list:\n";
        cin>>num;
        head->num = num;
        head->next = NULL;
        preptr = head;
        for(i=2; i<=n; i++)
        {
            newnode = (struct node *)malloc(sizeof(struct node));
            cin>>num;
            newnode->num = num;
            newnode->next = NULL;	
            preptr->next = newnode;	
            preptr = newnode;   		
        }
        preptr->next = head; 		//linking last node with head node
    }
}
void display()//function to display list
{
    struct node *tmp;
    int n = 1;
    
    if(head == NULL)
    {
        cout<<"List is empty";
    }
    else
    {
        tmp = head;
        
        cout<<"\nCircular linked list data:\n";
        do {
            cout<<tmp->num<<" ";
            tmp = tmp->next;
            n++;
        }while(tmp != head);
    }
}
void insertSpecific(int num, int pos)//function to insert element at specific position
{
    struct node *newnode, *curNode;
    int i;

    if(head == NULL)
    {
        cout<<"List is empty";
    }
    else
    {
        newnode = (struct node *)malloc(sizeof(struct node));
        newnode->num = num;
        curNode = head;
        for(i=0; i<=pos-3; i++)
        {
            curNode = curNode->next;
        }
        newnode->next = curNode->next;
        curNode->next = newnode;
    }
} 


int main()//main function
{
    int n,num,pos;
    head = NULL;
    cout<<"Enter the size of circular linked list: ";
    cin>>n;
    make(n); 
    display();
	cout<<"\nEnter data to be inserted : ";
    cin>>num;
    cout<<"Enter position where you want to enter the data:\n";
    cin>>pos;
    cout<<"\nAfter insertion data at specific position in list is:";  
    insertSpecific( num, pos);
    display();	
    return 0;
}
Output:
Enter the size of circular linked list: 5
Enter data of the list:
21
22
24
25
26

Circular linked list data:
21 22 24 25 26 
Enter data to be inserted at end: 23
Enter position where you want to enter the data:
3

After insertion data at specific position in list is:
Circular linked list data:
21 22 23 24 25 26

Want to learn more Data Structure?