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.

Insertion at end in doubly linked list

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.

Insertion at end in dobuly linked list in C++

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

Program for insertion at end in doubly linked list in C++

#include <iostream>
#include <stdlib.h>
using namespace std;

struct node {
    int num;
    struct node * preptr;
    struct node * nextptr;
}*stnode, *ennode;
 

void Listcreation(int n);
void LinsertNodeAtEnd(int num);
void displayList(int a);

int main()
{
    int n,num1,a;
    stnode = NULL;
    ennode = NULL;
	
    cout<<" Input the number of nodes : ";
    cin>>n;
    Listcreation(n); 
    a=1;
    displayList(a);
    cout<<" Input data for the last node : ";
    cin>>num1;
    LinsertNodeAtEnd(num1);
    a=2;
    displayList(a);
    return 0;
}
 
void Listcreation(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 LinsertNodeAtEnd(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 displayList(int m)
{
    struct node * tmp;
    int n = 1;
    if(stnode == NULL)
    {
        cout<<" No data found in the List yet.";
    }
    else
    {
        tmp = stnode;
        if (m==1)
        {
        cout<<"\n Data entered in the list are :\n";
        }
        else
        {
         cout<<"\n After insertion the new list are :\n";   
        }
        while(tmp != NULL)
        {
            cout<<" node" << n<<": "<< tmp->num<<endl;
            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