/* Ajith - Syntax Higlighter - End ----------------------------------------------- */

## 3.01.2012

### Deletion of a Node from Doubly Linked List

Previous Article: Inserting a Node in Doubly Linked List.

Deletion of a Node
Let us say our current Doubly Linked List is as shown in Figure-1.
 Figure 1: Current Doubly Linked List

• Deleting First Node of the List
• Now we have to delete First Node from the List shown in Figure-1. Because of this operation HEAD and Node-2 are affected.
In NODE-2 - NEXT variable remains unchanged and PREV variable should now point to NULL since it is the first Node in the List.
Decrement LENGTH variable in HEAD so that it maintains proper count of Nodes in the List.
Pseudocode:
HEAD->FIRST = HEAD->FIRST->NEXT

NODE-2->PREV = NULL

decrement(HEAD->LENGTH)
Output:
 Figure 2: After deleting the First Node in the List.

• Deleting Middle Node from the List
• Now let us delete NODE-2 from the List shown in Figure-1.Because of this operation NODE-1 and NODE-3 will be affected.
Using a temporary Node pointer curPtr we have to traverse until NODE-2.
In NODE-1 - PREV variable remains unchanged and NEXT variable should point to NODE-3 (i.e. curPtr->PREV->NEXT = curPtr->NEXT). As we know curPtr is at Node-2 so curPtr->PREV points to NODE-1 and hence curPtr->PREV->NEXT is equivalent to NODE-1->NEXT.
In NODE-3 - NEXT variable remains unchanged and PREV variable should point to NODE-1 (i.e. curPtr->NEXT->PREV = curPtr->PREV). Since curPtr is at NODE-2 so curPtr->NEXT points to NODE-3 and hence curPtr->NEXT->PREV is equivalent to NODE-3->PREV.
Decrement LENGTH variable in HEAD so that it maintains the proper count of Nodes in the List.
Pseudocode:
curPtr->PREV->NEXT = curPtr->NEXT

curPtr->NEXT->PREV = curPtr->PREV

decrement(HEAD->LENGTH)
Output:
 Figure 3: After Deleting NODE-2 in the List.

• Deleting Last Node in the List
• Now let us delete Last Node(NODE-3) from the List in Figure-1. Only NODE-2 is affected because of this operation.
Using a temporary Node pointer curPtr we have to traverse until the end Node of the List. So curPtr is now pointing to NODE-3.
In NODE-2- PREV variable remains unchanged and NEXT variable has to point to NULL (i.e curPtr->PREV->NEXT = NULL). Since curPtr is pointing to NODE-3 curPtr->PREV points to NODE-2 and hence curPtr->PREV->NEXT is equivalent to NODE-2 -> NEXT.
Decrement the LENGTH variable in HEAD so that it maintains the proper count of Nodes in the List.
Pseudocode:
curPtr->PREV->NEXT = NULL

decrement(HEAD->LENGTH)
Output:
 Figure 4: After Deleting Last Node from the List.

Let us see sample 'C' code to the deletion of a Node operation
retVal
{
retVal ret = SUCCESS;
UINT32 i;

listNode *curPtr;

{

if (loc == 1)
{

}
else
{
for(i=1; i<loc; i++)
curPtr = curPtr->next;

curPtr->prev->next = curPtr->next;

if(curPtr->next)
curPtr->next->prev = curPtr->prev;
}

dlist_freeNode(curPtr);
}