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
Method 1
Method 2
Method 1
Run
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node *prev;
};
int listSize = 0;
void insert(Node **head, int data)
{
Node *newNode = new Node();
newNode->data = data;
newNode->next = *head;
newNode->prev = NULL;
if (*head != NULL)
(*head)->prev = newNode;
*head = newNode;
listSize++;
}
void insertMiddle(Node **head, int data)
{
Node *newNode = new Node();
newNode->data = data;
if (*head == NULL)
{
insert(head, data);
return;
}
int mid = (listSize % 2 == 0) ? (listSize / 2) : (listSize + 1) / 2;
if (mid == listSize)
{
newNode->next = NULL;
newNode->prev = *head;
(*head)->next = newNode;
listSize++;
return;
}
Node *temp = *head;
while (--mid)
{
temp = temp->next;
}
(temp->next)->prev = newNode;
newNode->prev = temp;
newNode->next = temp->next;
temp->next = newNode;
listSize++;
}
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
Method 2
Run
#include<iostream>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node *prev;
};
class LinkedList
{
private:
Node *head;
int listSize; // Member variable for the size of the linked list
public:
LinkedList() : head(nullptr), listSize(0) {} // Constructor
int calcSize() const; // Function declaration for size calculation
void insert(int data);
void insertMiddle(int data);
void display() const; // Make the display function const
};
// Use member variable listSize for size calculation
int LinkedList::calcSize() const
{
return listSize;
}
void LinkedList::insert(int data)
{
Node *newNode = new Node();
newNode->data = data;
newNode->next = head;
newNode->prev = nullptr;
if (head != nullptr)
head->prev = newNode;
head = newNode;
listSize++;
}
void LinkedList::insertMiddle(int data)
{
Node *newNode = new Node();
newNode->data = data;
if (head == nullptr)
{
insert(data);
return;
}
int mid = (listSize % 2 == 0) ? (listSize / 2) : (listSize + 1) / 2;
if (mid == listSize)
{
newNode->next = nullptr;
newNode->prev = head;
head->next = newNode;
listSize++;
return;
}
Node *temp = head;
while (--mid)
{
temp = temp->next;
}
(temp->next)->prev = newNode;
newNode->prev = temp;
newNode->next = temp->next;
temp->next = newNode;
listSize++;
}
void LinkedList::display() const
{
cout << "\n\n";
Node *end = nullptr;
Node *node = head;
cout << "\nList in forward direction: ";
while (node != nullptr)
{
cout << node->data << " ";
end = node;
node = node->next;
}
cout << "\nList in backward direction: ";
while (end != nullptr)
{
cout << end->data << " ";
end = end->prev;
}
}
int main()
{
LinkedList doubly_list;
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
Method 1
Method 2
Method 1
Run
#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
Method 2
Run
#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
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Doubly Linked List
- Introduction to Doubly Linked list in Data Structure
Click Here - Doubly Linked List in –
- Insertion in doubly linked list –
- Insertion at beginning in doubly linked list –
- Insertion at end in doubly linked list –
- Insertion at nth node in doubly linked list –
- Deletion in doubly linked list –
- Deletion from beginning in doubly linked list :
- Deletion from nth in doubly linked list :
- Deletion from end in doubly linked list :
- Insertion and Deletion in a doubly linked list :
- Insertion in the middle in a doubly linked list :
Doubly Linked List
- Introduction to Doubly Linked list in Data Structure
- Doubly Linked List in – C | C++ | Java
- Insertion in doubly linked list – C | C++ | Java
- Deletion in doubly linked list – C | C++ | Java
- Insertion and Deletion in doubly linked list – C | C++ | Java
- Insertion in the middle in a doubly linked list – C | C++ | Java
Login/Signup to comment