﻿ C++ - Insert new node at the middle of a Doubly Linked List

# C++ Linked List Exercises: Insert new node at the middle of a Doubly Linked List

## C++ Linked List: Exercise-21 with Solution

Write a C++ program to insert a new node at the middle of a given Doubly Linked List.

Test Data:
Doubly linked list is as follows:
---------------------------------
Traversal in Forward direction: Orange White Green Red
Traversal in Reverse direction: Red Green White Orange
Insert a new node at the middle position of the said Doubly linked list:
-----------------------------------------------------------------------
Traversal in Forward direction: Orange White Pink Green Red
Traversal in Reverse direction: Red Green Pink White Orange
Insert another new node at the middle position of the said Doubly linked list:
-----------------------------------------------------------------------------
Traversal in Forward direction: Orange White Pink Black Green Red
Traversal in Reverse direction: Red Green Black Pink White Orange

Sample Solution:

C++ Code:

``````#include <iostream>

using namespace std;

// A doubly linked list node
struct Node {
string data;
struct Node* next;
struct Node* prev;
};

//Append node at the front of the list
{
//Create a new node and allocate memory.
struct Node* newNode = new Node;

//assign data to new node
newNode->data = new_data;

// A new node has been added with the name head and the previous node
// set to null, since it is being added at the front.
newNode->prev = NULL;

}

Node* new_Node = new Node();
new_Node->data = data;
return;
}
int size = 0;

// calculate length of the linked list
//, i.e, the number of nodes
while (ptr != NULL) {
size++;
ptr = ptr->next;
}

// find middle position
int mid_pos = (size % 2 == 0) ? (size/2) : (size+1)/2;
if(mid_pos == size){
new_Node->next = NULL;
size++;
return;
}
while(--mid_pos){
temp = temp->next;
}

(temp->next)->prev = new_Node;
new_Node->prev = temp;
new_Node->next = temp->next;
temp->next = new_Node;
size++;

}

// Following function display contents of the doubly linked list
{
Node* last_node;
cout << "\nTraversal in Forward direction: ";
cout << " " << head->data << " ";
}
cout << "\nTraversal in Reverse direction: ";
while (last_node != NULL) {
cout << " " << last_node->data << " ";
last_node = last_node->prev;
}
}

//main program
int main() {
cout<<"Doubly linked list is as follows: ";
cout<<"\n---------------------------------";
cout<<"\n\nInsert a new node at the middle position of the said Doubly linked list:";
cout<<"\n-----------------------------------------------------------------------";
cout<<"\n\nInsert another new node at the middle position of the said Doubly linked list:";
cout<<"\n-----------------------------------------------------------------------------";
cout<<endl;
return 0;
}
``````

Sample Output:

```Doubly linked list is as follows:
---------------------------------
Traversal in Forward direction:  Orange  White  Green  Red
Traversal in Reverse direction:  Red  Green  White  Orange

Insert a new node at the middle position of the said Doubly linked list:
-----------------------------------------------------------------------
Traversal in Forward direction:  Orange  White  Pink  Green  Red
Traversal in Reverse direction:  Red  Green  Pink  White  Orange

Insert another new node at the middle position of the said Doubly linked list:
-----------------------------------------------------------------------------
Traversal in Forward direction:  Orange  White  Pink  Black  Green  Red
Traversal in Reverse direction:  Red  Green  Black  Pink  White  Orange

```

Flowchart:

CPP Code Editor:

Previous C++ Exercise: Middle element of a Doubly Linked List.

What is the difficulty level of this exercise?

﻿

## C++ Programming: Tips of the Day

How to replace all occurrences of a character in string?

std::string doesn't contain such function but you could use stand-alone replace function from algorithm header.

```#include <algorithm>
#include <string>

void some_func() {
std::string s = "example string";
std::replace( s.begin(), s.end(), 'x', 'y'); // replace all 'x' to 'y'
}
```

Ref: https://bit.ly/3niU71x