Deletion from End in Doubly Linked List in C++

How to delete element from end in doubly linked list in C++?

Doubly Linked list is one of the variation of Linked list which is a linear data structure. Double Linked List was introduced because of one major drawback of singly linked list, i.e; we can only traverse the singly linked list in a single direction as it only hold the address of the next node, but not of the previous node. But in  Doubly Linked List, there are two pointer variables and hence we store the data of both the previous node and of the next node, which makes it more suitable to use than its predecessor.

deletion from end in doubly linked list

Steps to delete from end in doubly linked list in C++

Following steps are involved in deletion of  last node from a doubly linked list  :-

1.) Traverse till the last node

2.) Change the next of  last second node with null.

3.) Delete the last node

Defining doubly linked list in C++

struct Node 
{
  int Data;
  Struct Node* next;
  Struct Node* prev;
};
deletion from end in doubly linked list in C++

Algorithm to delete from end in doubly linked list in C++

  •  IF HEAD = NULL
  •  EXIT
  •  ELSE SET TEMP = HEAD
  •  REPEAT WHILE TEMP->NEXT != NULL
  •  SET TEMP = TEMP->NEXT
  •  SET TEMP ->PREV-> NEXT = NULL
  •  FREE TEMP
  •  EXIT

Program to delete from 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;
}
*starrt_node, *end_node;
 

void Listcreation(int n);
void DeleteLastnode();
void display(int a);

int main()
{
    int n,num1,a,insPlc;
    starrt_node = NULL;
    end_node = NULL;
             
    cout<<" Enter the number of nodes: ";
    cin>>n;
    Listcreation(n); 
    a=1;
    display(a);
    DeleteLastnode();
        a=2;
    display(a);
    return 0;
}
 
void Listcreation(int n)
{
    int i, num;
    struct node *fnNode;
 
    if(n >= 1)
    {
        starrt_node = (struct node *)malloc(sizeof(struct node));
        if(starrt_node != NULL)
        {
            cout<<" Enter data for node 1: "; // assigning data in the first node
            cin>>num;
            starrt_node->num = num;
            starrt_node->preptr = NULL;
            starrt_node->nextptr = NULL;
            end_node = starrt_node;
            for(i=2; i<=n; i++)
            {
                fnNode = (struct node *)malloc(sizeof(struct node));
                if(fnNode != NULL)
                {
                    cout<<" Enter data for node "<<i<<": ";
                    cin>>num;
                    fnNode->num = num;
                    fnNode->preptr = end_node;    // new node is linking with the previous node
                    fnNode->nextptr = NULL;       // set next address of fnnode is NULL
                    end_node->nextptr = fnNode;   // previous node is linking with the new node
                    end_node = fnNode;            // assign new node as last node
                }
                else
                {
                    cout<<" Memory can not be allocated.";
                    break;
                }
            }
        }
        else
        {
            cout<<" Memory can not be allocated.";
        }
    }
}

void DeleteLastnode()
{
    struct node * NodeToDel;
 
    if(end_node == NULL)
    {
        cout<<" Delete is not possible. No data in the list.\n";
    }
    else
    {
        NodeToDel = end_node;
        end_node = end_node->preptr;    // move the previous address of the last node to second last node
        end_node->nextptr = NULL;      // set the next address of last node to NULL
        free(NodeToDel);              // delete the last node
    }
}

void display(int m)
{
    struct node * tmp;
    int n = 1;
    if(starrt_node == NULL)
    {
        cout<<" No data found in the list yet.";
    }
    else
    {
        tmp = starrt_node;
        if (m==1)
        {
        cout<<"\n Data entered in the list are :\n";
        }
        else
        {
         cout<<"\n After deletion the new list are :\n";   
        }
        while(tmp != NULL)
        {
            cout<<" node "<< n<<": "<< tmp->num<<endl;
            n++;
            tmp = tmp->nextptr; 
        }
    }
}
Output:
 Enter the number of nodes: 5
 Enter data for node 1: 11
 Enter data for node 2: 22
 Enter data for node 3: 33
 Enter data for node 4: 44
 Enter data for node 5: 55

 Data entered in the list are :
 node 1: 11
 node 2: 22
 node 3: 33
 node 4: 44
 node 5: 55

 After deletion the new list are :
 node 1: 11
 node 2: 22
 node 3: 33
 node 4: 44