Insertion in the middle of Linked List in C++

Program for Singly Linked List Insertion and Deletion in C++

Lets try to understand how we can do Insertion and deletion Operations on a Linked List in C++. We will look at most effective methods to do so.

Linked List

Methods Discussed

We will be covering the following methods –

  1. Approach 1: With additional Global size variable
  2. Approach 2: Without additional Global size variable
New Insertion in the middle of Linked List in C++

Approach 1: With additional Global Size Variable

  • Method 1: Using external functions
  • Method 2: Using member functions
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;
    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){
        newNode->data = data;
        newNode->next = *head;
        *head = newNode;
        size++;
        return;
    }
    
    // otherwise
    Node* temp = *head;
    
    // find correct insertion position for middle
    int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;
    
    // traverse to current mid position
    while(--mid){
        temp = temp->next;
    }
    
    newNode->next = temp->next;
    temp->next = newNode;
    size++;
    
}

void display(Node* node)
{ 
    cout << "Linked List : \n";

    // as linked list will end when Node is Null
    while(node!=NULL){
        cout << node->data << " "; 
        node = node->next; 
    } 
    cout << "\n\n"; 
}

int main()
{
    Node* head = NULL;

    insert(&head,25);
    insert(&head,5);

    display(head); 

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

    insertMiddle(&head, 20);
    display(head); 
    
    insertMiddle(&head, 15);
    display(head); 

    return 0; 
}

Output

Linked List : 
5 25 

Linked List : 
5 10 25 

Linked List : 
5 10 20 25 

Linked List : 
5 10 15 20 25
Run
#include<iostream>
using namespace std;

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

class LinkedList
{
    private:
        Node* head;
    public:
        LinkedList() { // constructor
        head = NULL;
    }
        int getCurrSize();
        void insertMiddle(int data);
        void insert(int data);
        void display();
};
int size = 0;
void LinkedList::insert(int data){
    
    Node* newNode = new Node();
    
    newNode->data = data;
    newNode->next = head;
    head = newNode;
    
    size++;
}
void LinkedList::insertMiddle(int data){
    
    Node* newNode = new Node();
    newNode->data = data;
    
    // if the LL was empty
    if(head == NULL){
        newNode->data = data;
        newNode->next = head;
        head = newNode;
        size++;
        return;
    }
    
    // otherwise
    Node* temp = head;
    
    // find correct insertion position for middle
    int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;
    
    // traverse to current mid position
    while(--mid){
        temp = temp->next;
    }
    
    newNode->next = temp->next;
    temp->next = newNode;
    size++;
    
}

void LinkedList::display()
{ 
    cout << "Linked List : \n";
    
    Node* node = head;
    // as linked list will end when Node is Null
    while(node!=NULL){
        cout << node->data << " "; 
        node = node->next; 
    } 
    cout << "\n\n"; 
} 

int main() { 
    LinkedList* list = new LinkedList(); 
    list->insert(25);
    list->insert(5);

    list->display(); 

    list->insertMiddle(10);
    list->display(); 

    list->insertMiddle(20);
    list->display(); 
    
    list->insertMiddle(15);
    list->display();

    return 0; 
}

Output

Linked List : 
5 25 

Linked List : 
5 10 25 

Linked List : 
5 10 20 25 

Linked List : 
5 10 15 20 25

Approach 2: Without additional Global Size Variable

  • Method 1: Using external functions
  • Method 2: Using member functions
#include<iostream>
using namespace std;

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

int getCurrSize(Node* node){
    int size=0;

    while(node!=NULL){
        node = node->next;
        size++;
    }
    return size;
}

void insert(Node** head, int data){
    
    Node* newNode = new Node();
    
    newNode->data = data;
    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){
        newNode->data = data;
        newNode->next = *head;
        *head = newNode;
        return;
    }
    
    // otherwise
    Node* temp = *head;
    
    int size = getCurrSize(*head);
    
    // find correct insertion position for middle
    int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;
    
    // traverse to current mid position
    while(--mid){
        temp = temp->next;
    }
    
    newNode->next = temp->next;
    temp->next = newNode;
    
}

void display(Node* node)
{ 
    cout << "Linked List : \n";

    // as linked list will end when Node is Null
    while(node!=NULL){
        cout << node->data << " "; 
node = node->next; } cout << "\n\n"; } int main() { Node* head = NULL; insert(&head,25); insert(&head,5); display(head); insertMiddle(&head, 10); display(head); insertMiddle(&head, 20); display(head); insertMiddle(&head, 15); display(head); return 0; }

Output

Linked List : 
5 25 

Linked List : 
5 10 25 

Linked List : 
5 10 20 25 

Linked List : 
5 10 15 20 25
#include<iostream>
using namespace std;

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

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

int LinkedList::getCurrSize(){
    int size=0;
    Node* temp = head;

    while(temp!=NULL){
        temp = temp->next;
        size++;
    }
    return size;
}

void LinkedList::insert(int data){
    
    Node* newNode = new Node();
    
    newNode->data = data;
    newNode->next = head;
    head = newNode;
}
void LinkedList::insertMiddle(int data){
    
    Node* newNode = new Node();
    newNode->data = data;
    
    // if the LL was empty
    if(head == NULL){
        newNode->data = data;
        newNode->next = head;
        head = newNode;
        return;
    }
    
    // otherwise
    Node* temp = head;
    
    int size = getCurrSize();
    
    // find correct insertion position for middle
    int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;
    
    // traverse to current mid position
    while(--mid){
        temp = temp->next;
    }
    
    newNode->next = temp->next;
    temp->next = newNode;
    
}

void LinkedList::display()
{ 
    cout << "Linked List : \n";
    
    Node* node = head;
    // as linked list will end when Node is Null
    while(node!=NULL){
        cout << node->data << " "; 
node = node->next; } cout << "\n\n";
}

int main() {
LinkedList* list = new LinkedList();
list->insert(25); list->insert(5); list->display(); list->insertMiddle(10); list->display(); list->insertMiddle(20); list->display(); list->insertMiddle(15); list->display(); return 0; }

Output

Linked List : 
5 25 

Linked List : 
5 10 25 

Linked List : 
5 10 20 25 

Linked List : 
5 10 15 20 25

Singly Linked List

  • Introduction to Linked List in Data Structure
    Click Here
  • Linked List in –
    C | C++ | Java
  • Singly Linked List in –
    C | C++ | Java
  • Insertion in singly Linked List –
    C | C++ | Java
  • Insertion at beginning in singly Linked List  –
    C | C++Java
  • Insertion at nth position in singly Linked List  –
    C | C++Java
  • Insertion at end in singly Linked List  –
    C | C++Java
  • Deletion in singly Linked List  –
    C | C++Java
  • Deletion from beginning in singly linked list :
    C | C++ | Java
  • Deletion from nth position in singly linked list :
    C | C++ | Java
  • Deletion from end in singly linked list :
    C | C++ | Java
  • Linked List Insertion and Deletion –
    C | C++Java
  • Reverse a linked list without changing links between nodes (Data reverse only) –
    C | C++Java
  • Reverse a linked list by changing links between nodes –
    C | C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Print reverse of a linked list without actually reversing –
    C |C++Java
  • Insertion in the middle Singly Linked List –
    C | C++Java
  • Insertion in a Sorted Linked List –
    C | C++Java
  • Delete alternate nodes of a Linked List –
    C | C++Java
  • Find middle of the linked list –
    C | C++Java
  • Reverse a linked list in groups of given size –
    C | C++Java
  • Find kth node from end of the linked list –
    C | C++Java
  • Append the last n nodes of a linked list to the beginning of the list –
    C | C++Java
  • Check whether linked list is palindrome or not –
    C | C++Java
  • Fold a Linked List –
    C | C++Java
  • Insert at given Position –
    C | C++Java
  • Deletion at given Position –
    C | C++Java

Singly Linked List

  • Introduction to Linked List in Data Structure
  • Linked List in – C | C++ | Java
  • Singly Linked List in – C | C++ | Java
  • Insertion in singly Linked List – C | C++ | Java
    • Insertion at beginning in singly Linked List  – C | C++Java
    • Insertion at nth position in singly Linked List  – C | C++Java
    • Insertion at end in singly Linked List  – C | C++Java
  • Deletion in singly Linked List  – C | C++Java
    • Deletion from beginning in singly linked list : C | C++ | Java
    • Deletion from nth position in singly linked list : C | C++ | Java
    • Deletion from end in singly linked list : C | C++ | Java
  • Reverse a linked list without changing links between nodes (Data reverse only) – C | C++Java
  • Linked List Insertion and Deletion – C | C++Java
  • Reverse a linked list by changing links between nodes – C | C++Java
  • Linked List insertion in the middle – C | C++Java
  • Print reverse of a linked list without actually reversing – C |C++ | Java
  • Search an element in a linked list – C | C++Java
  • Insertion in a Sorted Linked List – C | C++Java
  • Delete alternate nodes of a Linked List – C | C++Java
  • Find middle of the linked list – C | C++Java
  • Reverse a linked list in groups of given size – C | C++Java
  • Find kth node from end of the linked list – C | C++Java
  • Append the last n nodes of a linked list to the beginning of the list – C | C++Java
  • Check whether linked list is palindrome or not – C | C++Java
  • Fold a Linked List – C | C++Java
  • Insert at a given position – C | C++Java
  • Delete at a given position – C | C++Java