# 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 – 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 ## 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->prev = NULL;

// changing the new head to this freshly entered node
size++;
}
void insertMiddle(Node** head, int data){

Node* newNode = new Node();
newNode->data = data;

// if the LL was empty
// using insert function to insert at start
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;
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;

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;
};

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

Node* newNode = new Node();

newNode->data = data;
newNode->prev = NULL;

// changing the new head to this freshly entered node
size++;
}

Node* newNode = new Node();
newNode->data = data;

// if the LL was empty
// 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;
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
{
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()
{

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->prev = NULL;

// changing the new head to this freshly entered node
}
void insertMiddle(Node** head, int data){

Node* newNode = new Node();
newNode->data = data;

// if the LL was empty
// using insert function to insert at start
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;
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;

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;
};

{
private:
public:
LinkedList() { // constructor
}
int calcSize();
void insert(int data);
void insertMiddle(int data);
int getLength();
void display();
};

Node* newNode = new Node();

newNode->data = data;
newNode->prev = NULL;

// changing the new head to this freshly entered node
}

Node* newNode = new Node();
newNode->data = data;

// if the LL was empty
// 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;
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 len = 0;

Node* node = head;

while(node!=NULL){
node = node->next;
len++;
}
return len;
}
//function to print the doubly linked list
{
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()
{

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
• 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