Deletion of a Node from Doubly Linked List

This article is part of article series - "Datastructures".

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 HEAD - FIRST variable should now point to NODE-2 (i.e HEAD->FIRST = HEAD->FIRST->NEXT). If you see HEAD->FIRST->NEXT actually HEAD->FIRST currently points to NODE-1 so HEAD->FIRST->NEXT is equivalent to NODE-1->NEXT which is NODE-2.

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
delNodeAtLoc(listHead *head, UINT32 loc)
{
    retVal ret = SUCCESS;
    UINT32 i;

    listNode *curPtr;

    if(head && head->first && loc && loc <= (head->length)) 
    {   
        curPtr = head->first;

        if (loc == 1)
        {   
            head->first = curPtr->next;

            if(head->first)
                head->first->prev = NULL;
        }   
        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);
        head->length--;
    }
    else
        ret = FAILURE;

    return ret;
}