Insertion in between of nodes in singly linked list in C++

Insertion in between the nodes in singly linked list in C++

How to perform insertion in between of nodes in  Singly Linked List in C++?

Insertion in between of nodes in singly linked list in C++ is a multiple step process. In this article we will learn these steps and algorithm for data insertion at desired position.

We can also perform insertion at beginning that is inserting an element in the beginning of linked list and insertion at end of the linked list. You can learn about this by clicking the button below

Steps to insert an element in between of nodes in singly linked list

Following steps are followed for insertion of an element at nth position in singly linked list.

1.)If there is no data in the head then exit

    • If(head==NULL)
      return

2.) Allocate space for a new node.

    • new_node = (struct node *) malloc(sizeof(struct node *));

  3.) In the space created for new node put the data in.

    • new_node->data = new_data

 4.)Traverse till the desired position and make point the pointer of new node where previous node is pointing.

    • new_node->ptr= prev_node->ptr

5.) Now point the pointer of previous node to the new node.

    • prev_node->ptr = new_node

Defining a singly linked list in C++

Nodes of singly linked list is created by using the code mentioned besides.
This set of code will construct linked list by creating each node of the list.

class Node  

    int data; 
    Node *next; 
}; 
Algorithm for insertion in between the nodes in singly linked list in c++

Algorithm to insert an element at nth position of singly linked list

  • IF PTR = NULL
  • EXIT
  • SET NEW_NODE = PTR
  • NEW_NODE → DATA = VAL
  • SET TEMP = HEAD
  • SET I = 0
  • REPEAT
  • TEMP = TEMP → NEXT
  • IF TEMP = NULL
  • EXIT
  • PTR → NEXT = TEMP → NEXT
  • TEMP → NEXT = PTR
  • SET PTR = NEW_NODE
  • EXIT

Program for insertion in between of nodes in singly linked list in C++

#include <iostream>
using namespace std;

struct node 
{
    int num;                
    node *nextptr;             
}*stnode; //node constructed

void createList(int n);                 
void insertNode(int num, int pos);	            
void display();                          
 
int main()
{
    int n,num,pos;
		
    cout<<"Enter the number of nodes: ";
    cin>>n;
    createList(n);
    cout<<"\nLinked list data: \n";		
    display();
    cout<<"\nEnter data you want to insert at the nth position: ";
    cin>>num;
    cout<<"Enter the position to insert new node : ";
    cin>>pos;
    insertNode( num, pos);
    cout<<"\nLinked list after insertion: \n";		
    display();

   return 0;
}
void createList(int n) //function to create linked list.
{
    struct node *frntNode, *tmp;
    int num, i;
 
    stnode = (struct node *)malloc(sizeof(struct node));
    if(stnode == NULL)        
    {
        cout<<"Memory can not be allocated";
    }
    else
    {
                                  
        cout<<"Enter the data for node 1: ";
        cin>>num;
        stnode-> num = num;      
        stnode-> nextptr = NULL; //Linking the address field to NULL
        tmp = stnode;
 
        for(i=2; i<=n; i++)
        {
            frntNode = (struct node *)malloc(sizeof(struct node)); 
 

            if(frntNode == NULL) //If frntnode is null no memory cannot be allotted
            {
                cout<<"Memory can not be allocated";
                break;
            }
            else
            {
                cout<<"Enter the data for node "<<i<<": "; // Entering data in nodes.
                cin>>num;
                frntNode->num = num;         
                frntNode->nextptr = NULL;    
                tmp->nextptr = frntNode;     
                tmp = tmp->nextptr;
            }
        }
    }
} 

void insertNode(int num, int pos)//fuction to add node in desired position
{
    int i;
    struct node *frntNode, *tmp;
    frntNode = (struct node*)malloc(sizeof(struct node));
    if(frntNode == NULL)
    {
       cout<<"Memory can not be allocated.";
    }
    else
    {
        frntNode->num = num; //Linking  the data 
        frntNode->nextptr = NULL;
        tmp = stnode;
        for(i=2; i<=pos-1; i++)
        {
            tmp = tmp->nextptr;
 
            if(tmp == NULL)
                break;
        }
        if(tmp != NULL)
        {
            frntNode->nextptr = tmp->nextptr;  //Linking the address part of new node
            tmp->nextptr = frntNode;   
        }
        else
        {
            cout<<"Data cannot be entered in that particular position\n";
        }
    }
}

void display() //function to print linked list
{
    struct node *tmp;
    if(stnode == NULL)
    {
        cout<<" No data found in the list";
    }
    else
    {
        tmp = stnode;
        cout<<"Linked List: ";
        while(tmp != NULL)
        {
            cout<<"\t"<<tmp->num;         
            tmp = tmp->nextptr;         
        }
    }
} 
Output:
Enter the number of nodes: 4
Enter the data for node 1: 11
Enter the data for node 2: 22
Enter the data for node 3: 33
Enter the data for node 4: 44

Linked list data: 
Linked List: 	11	22	33	44
Enter data you want to insert at the nth position: 55
Enter the position to insert new node : 4

Linked list after insertion: 
Linked List: 	11	22	33	55	44