Doubly Linked List Insertion in a the middle in C++

C++ Program to insert in the middle of a Doubly Linked List

We will be writing a C++ Program to insert in the middle of a Doubly Linked List in C++ check below –
nodes

We will look at the following approaches –

  • Approach 1: Global Size Variable for the size of doubly linked list
  • Approach 2: External function get the size of a doubly-linked list
C++ Program for Insertion in the middle of Doubly Linked List

Global Size Variable

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

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


int size = 0;
void insert(Node** head, int data){

    Node* newNode = new Node();

    newNode->data = data;
    newNode->next = *head;
    newNode->prev = NULL;
  
    //If the linked list already had atleast 1 node
    if(*head !=NULL)
        (*head)->prev = newNode;

    // changing the new head to this freshly entered node
    *head = newNode;
    size++;
}
void insertMiddle(Node** head, int data){
    
    Node* newNode = new Node();
    newNode->data = data;
    
    // if the LL was empty
    if(*head == NULL){
        // using insert function to insert at start
        insert(head,data);
        return;
    }
    
    // otherwise
    
    // find correct insertion position for middle
    int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;
    
    // will only happen when there is one node in Doubly Linked List
    // we will have to insert 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 = NULL;
        newNode->prev = *head;
        (*head)->next = newNode;
        size++;
        return;
    }

    Node* temp = *head;
    // traverse to current mid position
    while(--mid){
        temp = temp->next;
    }
    
    // (mid+1)th node prev to this newNode
    (temp->next)->prev = newNode;
    // newNode's prev to this current middle node
    newNode->prev = temp;
    // newNode's next to (mid+1)th node
    newNode->next = temp->next;
    // current mid node's next becomes this newNode
    temp->next = newNode;
    
    // this new inserted after the middle node successfully
    size++;
    
}

//function to print the doubly linked list
void display(Node* node) 
{ 
    cout << "\n\n";
    Node *end = NULL;
    cout << "\nList in forward direction: ";
    while (node != NULL) { 
        cout << node->data << " "; 
end = node;
node = node->next; } cout << "\nList in backward direction: "; while (end != NULL) { cout << end->data << " ";
end = end->prev; } } int main() { Node* head = NULL; insert(&head,120); insert(&head,0); display(head); insertMiddle(&head, 30); display(head); insertMiddle(&head, 60); display(head); insertMiddle(&head, 90); display(head); return 0; }

Output

List in forward direction: 0 120 
List in backward direction: 120 0 


List in forward direction: 0 30 120 
List in backward direction: 120 30 0 


List in forward direction: 0 30 60 120 
List in backward direction: 120 60 30 0 


List in forward direction: 0 30 90 60 120 
List in backward direction: 120 60 90 30 0 
#include<iostream>
using namespace std;

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

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

    Node* newNode = new Node();

    newNode->data = data;
    newNode->next = head;
    newNode->prev = NULL;
  
    //If the linked list already had atleast 1 node
    if(head !=NULL)
        head->prev = newNode;

    // changing the new head to this freshly entered node
    head = newNode;
    size++;
}
void LinkedList::insertMiddle(int data){
    
    Node* newNode = new Node();
    newNode->data = data;
    
    // if the LL was empty
    if(head == NULL){
        // using insert function to insert at start
        insert(data);
        return;
    }
    
    // otherwise
    
    // find correct insertion position for middle
    int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;
    
    // will only happen when there is one node in Doubly Linked List
    // we will have to insert 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 = NULL;
        newNode->prev = head;
        head->next = newNode;
        size++;
        return;
    }

    Node* temp = head;
    // traverse to current mid position
    while(--mid){
        temp = temp->next;
    }
    
    // (mid+1)th node prev to this newNode
    (temp->next)->prev = newNode;
    // newNode's prev to this current middle node
    newNode->prev = temp;
    // newNode's next to (mid+1)th node
    newNode->next = temp->next;
    // current mid node's next becomes this newNode
    temp->next = newNode;
    
    // this new inserted after the middle node successfully
    size++;
    
}

//function to print the doubly linked list
void LinkedList::display() 
{
    cout << "\n\n";
    
    Node *end = NULL;
    Node *node = head;
    
    cout << "\nList in forward direction: ";
    while (node != NULL) { 
        cout << node->data << " "; 
end = node;
node = node->next; } cout << "\nList in backward direction: "; while (end != NULL) { cout << end->data << " ";
end = end->prev; } } int main() { LinkedList* doubly_list = new LinkedList(); doubly_list->insert(120); doubly_list->insert(0); doubly_list->display(); doubly_list->insertMiddle(30); doubly_list->display(); doubly_list->insertMiddle(60); doubly_list->display(); doubly_list->insertMiddle(90); doubly_list->display(); return 0; }

Output

List in forward direction: 0 120 
List in backward direction: 120 0 


List in forward direction: 0 30 120 
List in backward direction: 120 30 0 


List in forward direction: 0 30 60 120 
List in backward direction: 120 60 30 0 


List in forward direction: 0 30 90 60 120 
List in backward direction: 120 60 90 30 0 

External function to calculate Size

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

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

int getLength(Node* node);

void insert(Node** head, int data){

    Node* newNode = new Node();

    newNode->data = data;
    newNode->next = *head;
    newNode->prev = NULL;
  
    //If the linked list already had atleast 1 node
    if(*head !=NULL)
        (*head)->prev = newNode;

    // changing the new head to this freshly entered node
    *head = newNode;
}
void insertMiddle(Node** head, int data){
    
    Node* newNode = new Node();
    newNode->data = data;
    
    // if the LL was empty
    if(*head == NULL){
        // using insert function to insert at start
        insert(head,data);
        return;
    }
    
    // otherwise
    int size = getLength(*head);
    
    // find correct insertion position for middle
    int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;
    
    // will only happen when there is one node in Doubly Linked List
    // we will have to insert 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 = NULL;
        newNode->prev = *head;
        (*head)->next = newNode;
        return;
    }

    Node* temp = *head;
    // traverse to current mid position
    while(--mid){
        temp = temp->next;
    }
    
    // (mid+1)th node prev to this newNode
    (temp->next)->prev = newNode;
    // newNode's prev to this current middle node
    newNode->prev = temp;
    // newNode's next to (mid+1)th node
    newNode->next = temp->next;
    // current mid node's next becomes this newNode
    temp->next = newNode;
    
    // this newNode inserted after the middle node successfully
}
int getLength(Node* node){
    int len = 0;

    while(node!=NULL){
        node = node->next;
        len++;
    }
    return len;
}
//function to print the doubly linked list
void display(Node* node) 
{ 
    cout << "\n\n";
    Node *end = NULL;
    cout << "\nList in forward direction: ";
    while (node != NULL) { 
        cout << node->data << " "; 
        end = node; 
        node = node->next; 
    }
    
    cout << "\nList in backward direction: ";

    while (end != NULL) { 
        cout << end->data << " "; 
        end = end->prev; 
    }
}

int main()
{
    Node* head = NULL;

    insert(&head,120);
    insert(&head,0);

    display(head); 

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

    insertMiddle(&head, 60);
    display(head); 
    
    insertMiddle(&head, 90);
    display(head); 

    return 0; 
}

Output

List in forward direction: 0 120 
List in backward direction: 120 0 

List in forward direction: 0 30 120 
List in backward direction: 120 30 0 

List in forward direction: 0 30 60 120 
List in backward direction: 120 60 30 0 

List in forward direction: 0 30 90 60 120 
List in backward direction: 120 60 90 30 0 
#include<iostream>
using namespace std;

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

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

void LinkedList::insert(int data){

    Node* newNode = new Node();

    newNode->data = data;
    newNode->next = head;
    newNode->prev = NULL;
  
    //If the linked list already had atleast 1 node
    if(head !=NULL)
        head->prev = newNode;

    // changing the new head to this freshly entered node
    head = newNode;
}
void LinkedList::insertMiddle(int data){
    
    Node* newNode = new Node();
    newNode->data = data;
    
    // if the LL was empty
    if(head == NULL){
        // using insert function to insert at start
        insert(data);
        return;
    }
    
    // otherwise
    int size = getLength();
    
    // find correct insertion position for middle
    int mid = (size % 2 == 0) ? (size/2) : (size+1)/2;
    
    // will only happen when there is one node in Doubly Linked List
    // we will have to insert 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 = NULL;
        newNode->prev = head;
        head->next = newNode;
        return;
    }

    Node* temp = head;
    // traverse to current mid position
    while(--mid){
        temp = temp->next;
    }
    
    // (mid+1)th node prev to this newNode
    (temp->next)->prev = newNode;
    // newNode's prev to this current middle node
    newNode->prev = temp;
    // newNode's next to (mid+1)th node
    newNode->next = temp->next;
    // current mid node's next becomes this newNode
    temp->next = newNode;
    
    // this newNode inserted after the middle node successfully
}
int LinkedList::getLength(){
    int len = 0;
    
    Node* node = head;

    while(node!=NULL){
        node = node->next;
        len++;
    }
    return len;
}
//function to print the doubly linked list
void LinkedList::display() 
{
    cout << "\n\n";
    
    Node *end = NULL;
    Node *node = head;
    
    cout << "\nList in forward direction: ";
    while (node != NULL) { 
        cout << node->data << " "; 
end = node;
node = node->next; } cout << "\nList in backward direction: "; while (end != NULL) { cout << end->data << " ";
end = end->prev; } } int main() { LinkedList* doubly_list = new LinkedList(); doubly_list->insert(120); doubly_list->insert(0); doubly_list->display(); doubly_list->insertMiddle(30); doubly_list->display(); doubly_list->insertMiddle(60); doubly_list->display(); doubly_list->insertMiddle(90); doubly_list->display(); return 0; }

Output

List in forward direction: 0 120 
List in backward direction: 120 0 


List in forward direction: 0 30 120 
List in backward direction: 120 30 0 


List in forward direction: 0 30 60 120 
List in backward direction: 120 60 30 0 


List in forward direction: 0 30 90 60 120 
List in backward direction: 120 60 90 30 0

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