Insertion at End in Doubly Linked list in C++
How to insert element at end in doubly linked list in C++?
Doubly Linked List is one of the linear data structure that we can use in place of array if we want to store a large amount of data. This is so because in doubly linked list the insertion and deletion operation are less time taking and more efficient than in an array.
Moreover in a doubly linked list we can traverse in both the directions that is towards head or towards tails, hence which makes the use of doubly linked list more likely than an array, when we are working on large amount of data.
Definition of doubly linked list in C++
struct Node { int Data; Struct Node* next; Struct Node* prev; };
Steps to insert element at end in doubly linked list in C++
1.) Allocate node.
2.)Put the data.
3.) Make next of this new node as Null
4.)This new node will become head if the linked list is empty.
5.)Else traverse till the last node.
6.)Change the next of last node from null to previous of new node.
Algorithm for insertion at end in doubly linked list in C++
- IF PTR = NULL
- SET NEW_NODE = PTR
- SET PTR = PTR -> NEXT
- SET NEW_NODE -> DATA = VAL
- SET NEW_NODE -> NEXT = NULL
- SET TEMP = START
- Repeat next while TEMP -> NEXT != NULL
- SET TEMP = TEMP -> NEXT
- SET TEMP -> NEXT = NEW_NODE
- SET NEW_NODE -> PREV = TEMP
- EXIT
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Program for insertion at end in doubly linked list in C++
This C++ program demonstrates how to insert a new node at the end of a doubly linked list. It creates a new node and connects it to the last node by updating the previous and next pointers. This maintains the bidirectional links and ensures the list remains properly structured.
#include<iostream>
#include<stdlib.h>
using namespace std;
struct node {
int num;
struct node * preptr;
struct node * nextptr;
}*stnode, *ennode;
void DlListcreation(int n);
void DlLinsertNodeAtEnd(int num);
void displayDlList();
int main()
{
int n,num1;
stnode = NULL;
ennode = NULL;
cout<<" Input the number of nodes : "; cin>>n;
DlListcreation(n);
displayDlList();
cout<<" Input data for the last node : "; cin>>num1;
DlLinsertNodeAtEnd(num1);
displayDlList();
return 0;
}
void DlListcreation(int n)
{
int i, num;
struct node *fnNode;
if(n >= 1)
{
stnode = (struct node *)malloc(sizeof(struct node));
if(stnode != NULL)
{
cout<<" Input data for node 1: "; // assigning data in the first node cin>>num;
stnode->num = num;
stnode->preptr = NULL;
stnode->nextptr = NULL;
ennode = stnode;
for(i=2; i<=n; i++)
{
fnNode = (struct node *)malloc(sizeof(struct node));
if(fnNode != NULL)
{
cout<<" Input data for node "<< i<<": "; cin>>num;
fnNode->num = num;
fnNode->preptr = ennode; // new node is linking with the previous node
fnNode->nextptr = NULL;
ennode->nextptr = fnNode; // previous node is linking with the new node
ennode = fnNode; // assign new node as last node
}
else
{
cout<<" Memory can not be allocated.";
break;
}
}
}
else
{
cout<<" Memory can not be allocated.";
}
}
}
void DlLinsertNodeAtEnd(int num)
{
struct node * newnode;
if(ennode == NULL)
{
cout<<" No data found in the list!\n"; } else { newnode = (struct node *)malloc(sizeof(struct node)); newnode->num = num;
newnode->nextptr = NULL; // set next address field of new node is NULL
newnode->preptr = ennode; // previous address of new node is linking with ending node
ennode->nextptr = newnode; // next address of ending node is linking with new node
ennode = newnode; // set the new node as ending node
}
}
void displayDlList ()
{
struct node *tmp;
tmp = stnode;
int n = 1;
while (tmp != NULL)
{
cout << " node " << n << ": " << tmp->num << "\n"; n++; tmp = tmp->nextptr; // current pointer moves to the next node
}
}Output:
Input the number of nodes : 5 Input data for node 1: 11 Input data for node 2: 22 Input data for node 3: 33 Input data for node 4: 44 Input data for node 5: 55 Data entered in the list are : node1: 11 node2: 22 node3: 33 node4: 44 node5: 55 Input data for the last node : 66 After insertion the new list are : node1: 11 node2: 22 node3: 33 node4: 44 node5: 55 node6: 66
Explanation:
- The program creates a doubly linked list dynamically using malloc() where each node has pointers to both previous and next nodes.
- The function DlListcreation() takes the number of nodes as input and builds the linked list by linking each new node to the previous one.
- The function DlLinsertNodeAtEnd() inserts a new node at the end of the list by updating the nextptr of the last node and the preptr of the new node.
- The displayDlList() function traverses the list from the start node and prints the data of each node sequentially.
- Overall, the code demonstrates dynamic memory allocation, proper pointer linking, and traversal in a doubly linked list structure.
Time and space complexity:
| Operation | Time Complexity | Space Complexity |
|---|---|---|
| Creating the Doubly Linked List | O(n) | O(n) |
| Inserting at End | O(1) | O(1) |
| Displaying the List | O(n) | O(1) |
To wrap it up:
Inserting a node at the end of a doubly linked list is a simple yet essential operation that strengthens your understanding of pointer manipulation. It ensures that the list grows dynamically while maintaining smooth navigation in both forward and backward directions.
By correctly updating the links between nodes, the new element becomes part of the list without disrupting its structure. This concept forms the foundation for more advanced linked list operations in C++ programming.
FAQs
Inserting at the end allows new data to be added after the last node, making it useful for maintaining the sequence of elements as they are inserted, similar to queue behavior.
In insertion at the end, the new node is added after the last element, whereas in insertion at the beginning, it becomes the first node. The pointer adjustments differ mainly for the prev and next references.
If a tail pointer is maintained, the time complexity is O(1) since insertion happens directly at the end. Without a tail pointer, it becomes O(n) as traversal from the head is needed.
A doubly linked list allows easy backward traversal and simplifies deletion or insertion operations since each node has both next and prev pointers, making manipulation at both ends more efficient.
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