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 Figure1.

Figure 1: Current Doubly Linked List 
 Deleting First Node of the List
Now we have to delete First Node from the List shown in Figure1. Because of this operation HEAD and Node2 are affected.
In HEAD  FIRST variable should now point to NODE2 (i.e HEAD>FIRST = HEAD>FIRST>NEXT). If you see HEAD>FIRST>NEXT actually HEAD>FIRST currently points to NODE1 so HEAD>FIRST>NEXT is equivalent to NODE1>NEXT which is NODE2.
In NODE2  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.
HEAD>FIRST = HEAD>FIRST>NEXT
NODE2>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 NODE2 from the List shown in Figure1.Because of this operation NODE1 and NODE3 will be affected.
Using a temporary Node pointer curPtr we have to traverse until NODE2.
In NODE1  PREV variable remains unchanged and NEXT variable should point to NODE3 (i.e. curPtr>PREV>NEXT = curPtr>NEXT). As we know curPtr is at Node2 so curPtr>PREV points to NODE1 and hence curPtr>PREV>NEXT is equivalent to NODE1>NEXT.
In NODE3  NEXT variable remains unchanged and PREV variable should point to NODE1 (i.e. curPtr>NEXT>PREV = curPtr>PREV). Since curPtr is at NODE2 so curPtr>NEXT points to NODE3 and hence curPtr>NEXT>PREV is equivalent to NODE3>PREV.
Decrement LENGTH variable in HEAD so that it maintains the proper count of Nodes in the List.
curPtr>PREV>NEXT = curPtr>NEXT
curPtr>NEXT>PREV = curPtr>PREV
decrement(HEAD>LENGTH)
Output:

Figure 3: After Deleting NODE2 in the List. 
 Deleting Last Node in the List
Now let us delete Last Node(NODE3) from the List in Figure1. Only NODE2 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 NODE3.
In NODE2 PREV variable remains unchanged and NEXT variable has to point to NULL (i.e curPtr>PREV>NEXT = NULL). Since curPtr is pointing to NODE3 curPtr>PREV points to NODE2 and hence curPtr>PREV>NEXT is equivalent to NODE2 > NEXT.
Decrement the LENGTH variable in HEAD so that it maintains the proper count of Nodes in the List.
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;
}
No comments :
Post a Comment
Your comments are moderated