Deletion in doubly linked list

Deletion in doubly linked list like insertion can be done at any location.  You can delete a node at the beginning, at the end, after a given node or at a given position. Node deletion in doubly linked list requires updating pointers of the previous and next node. You have to update NEXT pointer of previous node and PREV pointer of the node following the node to be deleted.

Deletion in doubly linked list at the beginning

The deletion of an existing node at the beginning is the easiest deletion operation. The FIRST pointer (which stores the address of the first node) is used for this. The following two pointer updates will do the deletion of a node at the beginning-

  1. The PREV pointer of the second node is set to NULL. It indicates that it doesn’t have any previous node after the first node is deleted (FIRST->NEXT->PREV=NULL)
  2. The FIRST pointer is updated with the NEXT of the FIRST node (FIRST=FIRST->NEXT)
Deletion in doubly linked list at beginning

Deletion at the End

The deletion of the last node of the doubly linked list is also as simple as deletion of the node at the beginning. The LAST pointer is used to do this deletion. These two pointer updates will delete the last node of a doubly linked list.

  1. The NEXT pointer of the previous node is updated with NULL (LAST->PREV->NEXT=NULL)
  2. LAST pointer is set to address of the previous node (LAST=LAST->PREV)
Deletion at end

Deletion of a Node with given value

The deletion of a node with given value involves search process to first find the address of the specified node. The search process returns the address of searched node in, say LOC pointer. These two pointer updates will complete the task

  1. The NEXT pointer of the previous node is updated with by NEXT pointer of the LOC pointer (LOC->PREV->NEXT=LOC->NEXT)
  2. The PREV pointer of the node next to the node referred by LOC pointer  is updated with address of PREV pointer of the LOC node (LOC->NEXT->PREV=LOC->PREV)
Deletion node of given value

Deletion at kth Position

The deletion of a node at Kth position in a doubly linked list involves traversal process to count the nodes traversed. While traversing the address of the previous node is maintained in a pointer, say, LOC.   When the count of traversed nodes becomes equal to K, traversal is terminated.  The node identified by LOC pointer is deleted with these pointer updates.

  1. The NEXT pointer of the previous node is updated with by NEXT pointer of the LOC pointer (LOC->PREV->NEXT=LOC->NEXT)
  2. The PREV pointer of the node next to the node referred by LOC pointer  is updated with address of PREV pointer of the LOC node (LOC->NEXT->PREV=LOC->PREV)
Deletion of node at given location

Be First to Comment

Leave a Reply

Your email address will not be published. Required fields are marked *