Deletion in Doubly Linked List in C++

Deletion in Doubly Linked List

What is deletion in doubly linked list in CPP programming?

Deletion in a doubly linked list in C++ can be simplified as deleting a node from an already constructed linked list. On the doubly linked list, we can perform three different types of deletion operation, these different types of deletion operation are :-

  • Deleting the beginning node from the list.
  • Deletion from specific position in doubly linked list.
  • Deletion from end in doubly linked list.

In this post, we will address what is the difference between these various forms of delete operations and how C++ programming can be used to perform them on a doubly linked list.

 

Types of Deletion in Doubly Linked list in C++?

Deletion from beginning

In the process of deletion from beginning we make the second node of the list as new head and free the previous head of the list

Deletion from specific position

In the process of deletion from specific position in doubly linked list we delete any node that user want to delete from the given linked list.

Deletion from end

In the process of deletion from specific position in doubly linked list we point the next pointer of last second node to NULL and then we will free the last node.

Types of deletion in doubly linked list

Deletion from beginning

Deletion from beginning

How to perform 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); } }
Type of deletion | From beginning

Deletion from specific position

Deletion from specific position

How to perform 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";
    }
} 
Type of deletion | From specific position

Deletion from end

Deletion from end

How to perform 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);              
    }
}
Type of deletion | From End