Deletion in Doubly Linked List in C++

May 15, 2025

Understanding Deletion in a Doubly Linked List in C++

Deletion in a doubly linked list in C++ involves removing a specific node from an existing list while ensuring that the links between the remaining nodes are properly maintained. In a doubly linked list, each node has pointers to both its previous and next nodes, making it easier to manage node connections during deletion.

  • Deleting the beginning node from the list.
  • Deletion from specific position in doubly linked list.
  • Deletion from end in doubly linked list.
Deletion in Doubly Linked List in C++

What is Deletion in a Doubly Linked List in C++ ?

  • Doubly linked lists are data structures that allow bidirectional traversal using two pointers: next and prev.
  • This structure makes deletion operations more manageable compared to singly linked lists, as it provides direct access to both the preceding and succeeding nodes.

Further, we will explore how deletion works in a doubly linked list, including the three main types of deletion operations, their implementation in C++, and key considerations.

Understanding Deletion in a Doubly Linked List

In a doubly linked list, each node consists of three components:

  1. Data: Stores the node’s value.
  2. Next Pointer: Points to the next node in the list.
  3. Previous Pointer: Points to the previous node in the list.

Deletion in a doubly linked list involves removing a specific node while maintaining the integrity of the remaining list by adjusting the next and prev pointers appropriately.

Types of Deletion in Doubly Linked list in C++

1. Deletion from beginning (Head Deletion)

  • Deleting the first node in a doubly linked list is a critical operation as it modifies the head pointer.
  • This operation is slightly more complex than in a singly linked list because we must also update the prev pointer of the new head to NULL.

When is it used?

When we need to remove the first element in the list, such as implementing stack or queue like structures where the front element is processed first.

Potential Issues:

If the list is empty, attempting to delete the head will cause a null pointer access error. Hence, always check for an empty list before proceeding.

2. Deleting a Node at a Specific Position

Deleting a node at a specific position in a doubly linked list requires precise pointer manipulation. It involves locating the node, adjusting the pointers of its previous and next nodes, and then freeing the node.

When is it used?

This operation is common in applications where nodes are arranged in a specific order, such as in priority queues or task schedulers.

Potential Issues:

If the specified position is out of bounds or the list is empty, the deletion may fail or cause unexpected behavior.

3. Deletion from end (Tail Deletion)

Deleting the last node in a doubly linked list is straightforward but requires traversal to the end of the list to access the last node and its previous node. After the last node is removed, the previous node becomes the new tail.

When is it used?

This operation is essential in scenarios where nodes are processed or removed in reverse order, such as in stack implementations.

Potential Issues:

If the list contains only one node, deleting it will result in an empty list. Ensure that the head pointer is also updated to NULL in such cases.

1. Deletion From Beginning In Doubly Linked List

To perform deletion from beginning in doubly linked list we will use the following steps:

  1. First we will create a doubly linked list.
  2. Now we will free the pointer that is pointing the head of the list and will make second node as head of the list.
void DeleteFirstNode()
{
    struct node * NodeToDel;
    if(start_node == NULL)
    {
        cout<<" Deletion is not possible. No data in the list.\n"; 
    } 
    else 
    {
        NodeToDel = start_node; 
        start_node = start_node->nextptr;    
        start_node->preptr = NULL;          
        free(NodeToDel);                   
    }
}
Deletion from beginning in Doubly Linked List in C++

Doubly Linked List in C++

Deletion from beginning in doubly linked list

Deletion from nth in doubly linked list

Learn DSA

Learn DSA with C++

2. Deletion From Specific Position In Doubly Linked List

To perform deletion from specific position in doubly linked list we will use the following steps:

  1. After creating a doubly linked list, traverse till the specific position.
  2. Assign the next pointer of the previous node to the next reference node.
  3. For the next target node the previous pointer is set to the address of the previous node. 
void deleteSpecific(int pos)
{
    struct node *curNode;
    int i;
 
    curNode = start_node;
    for(i=1; i<pos && curNode!=NULL; 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); 
    }
    else
    {
        cout<<" The given position is invalid!\n";
    }
}
deletion of target node in doubly linked list in c++

3. Deletion From End In Doubly Linked List

To perform deletion from end in doubly linked list we will use the following steps:

After creating a linked list with some data in it we will :

  1. Traverse till the end of the list using a node pointer.
  2. Link the next pointer of last second node with NULL.
  3. And now we will delete the last node.
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;    
        end_node->nextptr = NULL;      
        free(NodeToDel);              
    }
}
deletion from end in doubly linked list in c++

Conclusion

  • Deletion in a doubly linked list in C++ involves carefully managing node pointers to maintain the integrity of the list structure.
  • Whether removing the first node, a specific node, or the last node, the process requires adjusting both next and prev pointers to ensure that the remaining nodes stay properly connected.
  • By understanding the time and space complexity of each deletion operation, developers can effectively implement and optimize deletion functions, preventing common issues like memory leaks and null pointer exceptions.

Learn DSA

Learn DSA with C++

FAQ's Related Deletion in Doubly Linked List

Answer:

In a singly linked list, we only have a next pointer, so we can only traverse forward and need extra steps to update previous nodes. In a doubly linked list, we have both next and prev pointers, allowing direct access to both the previous and next nodes, making deletion operations more efficient.

Answer:

If the list is empty, any attempt to delete a node should be safely handled by checking if the head is NULL. If head is NULL, there is no node to delete, and the operation should terminate without errors.

Answer:

After deleting the first node, the head pointer must be updated to point to the next node in the list. If the list becomes empty (i.e., the deleted node was the only node), the head should be set to NULL.

Answer:

In a doubly linked list, to delete the last node, we need to traverse the entire list to access the second-last node and update its next pointer. This traversal takes O(n) time, making the overall time complexity O(n).

Answer:

  1. Deleting the only node in the list (head and tail both become NULL).
  2. Deleting the first node when the list has multiple nodes (head update required).
  3. Deleting the last node when the list has multiple nodes (tail update required).
  4. Attempting to delete a node from an empty list.
  5. Deleting a node at a position outside the valid range.