Doubly Linked List Deletion

Deleting from a doubly linked list requires that the deleted node’s predecessor, if any, be pointed to the deleted node’s successor and that the successor, if any, be set to point to the predecessor. This rather straight forward logic is shown in Figure 21. Once we locate the node to be deleted, we simply change its predecessor’s and successor’s pointers and recycle the node.

The pseudocode is shown in Algorithm 13.

Algorithm – 13 Double linked list delete

algorithm deleteDbl (ref list ,

val pDlt ,

ref dataout )

The algorithm deletes a node from a doubly linked list.

Pre list is metadata structure to a valid list

pDlt is a pointer to the node to be deleted

Post node deleted

1 dataout = pDlt->data

Check if not first node

2 if (pDlt->back not null)

Point predecessor to successor

1 pPred = pDlt->back

2 pPred->fore = pDlt->fore

3 else (First node)

Update head pointer

1 list.head = pDlt->fore

4 end if

Check if not last node

5 if (pDlt->fore not null)

Point successor to predecessor

1 pSucc = pDlt->fore

2 pSucc->back = pDlt->back

6 else (Last node)

Point rear to predecessor

1 list.rear = pDlt->back

7 end if

8 recycle (pDlt)

9 list.count = list.count - 1

10 return

end deleteDbl