Deletion of target node in doubly linked list in C++

How to delete any target node in doubly linked list in C++?

Doubly Linked List is the successor of the singly linked list linear data structure. Although Doubly Linked List is more useful than singly linked list in various manner, but it has its own drawbacks, one of which is that it requires a lot of data in comparison with singly linked list.

In this article let’s see one of the operation that you can perform on Doubly Linked List, i.e; a C++ Program for Deletion of nth node in Doubly Linked List

Deletion from nth in doubly linked list

Steps to delete a target node in doubly linked list in C++

Following steps are involved in deletion any target node from a doubly linked list  :-

  • Traverse till the target node.
  • Assign previous node’s next pointer to the next node of the target node.
  • For the next node of the target node, its previous pointer is assigned to the targets node’s previous node’s address.
  • Exit

Defining doubly linked list in C++

struct Node 
{
  int Data;
  Struct Node* next;
  Struct Node* prev;
};
Deletion of target node in doubly linked it in C++

Algorithm to delete any target node in doubly linked list in C++

  •  IF HEAD = NULL
  •  EXIT
  • ELSE SET TEMP = HEAD
  • Repeat Next Step while TEMP ->NODE!= POS
  • SET TEMP = TEMP -> NEXT
  • END Of LOOP
  • SET PTR = TEMP -> NEXT
  •  SET TEMP -> NEXT = PTR -> NEXT
  • SET PTR -> NEXT -> PREV = TEMP
  • FREE PTR
  • EXIT

Program to delete any target node in doubly linked list in C++

The program to delete any target node in a doubly linked list in C++ allows removal of a specific node from any position  beginning, middle, or end  by adjusting the previous and next pointers. It ensures the list remains properly linked after deletion, maintaining both forward and backward traversal.

Run

#include<iostream> 
using namespace std;

struct node {
    int num;
    struct node * preptr;
    struct node * nextptr;
}*start_node, *end_node;
 

void Listcreation(int n);
void DeleteFirstnode();
void DeleteLastnode();
void DeleteAnyNode(int pos);
void display(int a);

int main()
{
    int n,num1,a,insPlc;
    start_node = NULL;
   end_node= NULL;
         
    cout<<" Enter the number of nodes : "; cin>>n;
    Listcreation(n); 
    a=1;
    display(a);
    cout<<" Enter the position to delete a node : "; cin>>insPlc;

    
if(insPlc<1 || insPlc>n)
    {
     cout<<"\n Invalid position. Try again.\n "; } if(insPlc>=1 && insPlc<=n) { DeleteAnyNode(insPlc); a=2; display(a); } return 0; } void Listcreation(int n) { int i, num; struct node *fnNode; if(n >= 1)
    {
        start_node = (struct node *)malloc(sizeof(struct node));
 
        if(start_node != NULL)
        {
            cout<<" Enter data for node 1: "; // storing data in the first node cin>>num;
 
            start_node->num = num;
            start_node->preptr = NULL;
            start_node->nextptr = NULL;
            end_node= start_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;      // linking new nodes
                    fnNode->nextptr = NULL;        // setting the address of last node to 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 DeleteAnyNode(int pos)
{
    struct node* curNode;
    int i;

    curNode = start_node;
    for (i = 1; curNode != NULL && i < pos; i++) { curNode = curNode->nextptr;
    }

    if (pos == 1)
    {
        DeleteFirstnode();
    }
    else if (curNode == end_node)
    {
        DeleteLastnode();
    }
    else if (curNode != NULL)
    {
        curNode->preptr->nextptr = curNode->nextptr;
        curNode->nextptr->preptr = curNode->preptr;

        free(curNode); // Deleting the nth node
    }
    else
    {
        cout << "The given position is invalid!\n";
    }
}
 

void DeleteFirstnode()//deleting the first node
{
    struct node * NodeToDel;
    if(start_node == NULL)//checking if the first node is the last node or not
    {
        cout<<" Delete is not possible. No data in the list.\n"; } else { NodeToDel = start_node; start_node = start_node->nextptr;   
        start_node->preptr = NULL;     
        free(NodeToDel);           
    }
}

void DeleteLastnode()//deleting the last node
{
    struct node * NodeToDel;
 
    if(end_node== NULL)//checking whether the list has any nodes or not
    {
        cout<<" Delete is not possible. No data in the list.\n"; } else { NodeToDel = end_node; end_node= end_node->preptr;    
        end_node->nextptr = NULL;   
        free(NodeToDel);        
    }
}
void display(int m)
{
    struct node * tmp;
    int n = 1;
    if(start_node == NULL)
    {
        cout<<" No data found in the List yet.";
    }
    else
    {
        tmp = start_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; // current pointer moves to the next node
        }
    }
}

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
 Enter the position  to delete a node : 3

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

Explanation:

  • The program first creates a doubly linked list using dynamic memory allocation where each node stores data and links to its previous and next nodes.
  • It allows the user to delete a node at any given position by traversing to that node and updating the adjacent node links accordingly.
  • If the node to delete is the first or last one, special functions handle those cases to maintain proper list connectivity.
  • After deletion, the display function traverses the list and prints all the nodes to show the updated structure.
  • The program also includes validation to ensure that deletion only occurs at valid positions within the list.

Time and Space Complexity:

OperationTime ComplexitySpace Complexity
List CreationO(n)O(n)
Delete First NodeO(1)O(1)
Delete Last NodeO(1)O(1)
Delete Any Node (at position)O(n)O(1)
Display ListO(n)O(1)

To wrap it up:

The deletion of a target node in a doubly linked list involves adjusting the previous and next pointers of surrounding nodes to maintain the list’s structure. This method ensures that the node is removed efficiently without breaking the connections between other nodes, even in edge cases like deleting the first or last node.

Understanding this process strengthens your grasp of pointer manipulation and dynamic memory handling in C++. It also lays a strong foundation for mastering other linked list operations such as insertion, traversal, and reversal, which are essential for technical interviews and practical programming tasks.

FAQs

The main purpose is to remove a specific node based on its value or position without disturbing the structure of the remaining list by correctly updating the adjacent node pointers.

In a doubly linked list, you can directly access both the previous and next nodes, making deletion more efficient, while in a singly linked list you must traverse from the start to find the preceding node.

The time complexity is O(n) since you may need to traverse the list to locate the target node before performing the deletion operation.

You should check for edge cases like deleting the first or last node, ensure proper pointer reassignment, and free the node’s memory to prevent leaks or broken links.

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

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Doubly Linked List

  • Introduction to Doubly Linked list in Data Structure
    Click Here
  • Doubly Linked List in –
    C | C++ | Java
  • Insertion in doubly linked list –
    C | C++ | Java
  • Insertion at beginning in doubly linked list –
    C | C++ | Java
  • Insertion at end in doubly linked list –
    C | C++ | Java
  • Insertion at nth node in doubly linked list –
    C | C++ | Java
  • Deletion in doubly linked list  –
    C | C++ | Java
  • Deletion from beginning in doubly linked list :
  • Deletion from nth in doubly linked list :
    C | C++ | Java
  • Deletion from end in doubly linked list :
    C | C++ | Java
  • Insertion and Deletion in a  doubly linked list :
    C | C++ | Java
  • Insertion in the middle in a  doubly linked list :
    C | C++ | Java

Doubly Linked List