Operation 3 – Delete Node :

The delete node algorithm logically removes a node from the linked list by changing various link pointers and then physically deleting the node from dynamic memory. To logically delete a node, we must first locate the node itself. A delete node is located by knowing its address and its predecessor’s address. Once we locate the node to be deleted, we can simply change its predecessor’s link field to point to the deleted node’s successor. We then recycle the node back to dynamic memory. We need to be concerned, however, about deleting the only node in a list. Deleting the only node results in an empty list, so we must be careful that in this case the head is set to a null pointer.

The delete situations parallel those for add. We can delete the only node, the first node, a node in the middle of the list, or the last node of a list. As we explain below, these four situations reduce to only two combinations: delete the first node and delete any other node. In all cases, the node to be deleted is identified by a pointer (pLoc).


Operation 3a – Delete First Node or Only Node :
When we delete the first node, we must reset the head pointer to point to the first node’s successor and then recycle the memory for the deleted node. We can tell we are deleting the first node by testing the predecessor. If the predecessor is a null pointer, we are deleting the first node. This situation is diagrammed in Figure 15.

The statements to delete the first node are shown below. Recycle is the pseudocode command to return a node’s space to dynamic memory.

If you examine this logic carefully, you will note that it also applies when we are deleting the only node in the list. If the first node is the only node, then its link field is a null pointer. Because we move its link field (a null pointer) to the head pointer, the result is by definition an empty list.

Operation 3b – Delete Middle or Last Node Case :

Same logic applies to deleting any node in either the middle or at the end of the list. For both of these cases, we simply point the predecessor node to the successor of the node being deleted. The logic is shown in Figure 16.

We delete the last node automatically. When the node being deleted is the last node of the list, its null pointer is moved to the predecessor’s link field, making the predecessor the new logical end of the list. After the pointers have been adjusted, the current node is recycled.

The delete general case pseudocode is shown below in the inset of figure 16.

Operation 3c – Delete Node Algorithm :

The logic to delete a node is shown in Algorithm 3. The algorithm is given a pointer to the head of the list, to the node to be deleted, and to the delete node’s predecessor. It copies the deleted node’s data to a data out area in the

calling program and then adjusts the pointers before releasing the node’s memory.

Algorithm – 3 Linked list delete node

algorithm deleteNode (ref list ,

val pPre ,

val pLoc ,

ref dataOut )

Deletes data from a linked list and returns it to calling module.

Pre list is metadata structure to a valid list

pPre is a pointer to predecessor node

pLoc is a pointer to node to be deleted

dataOut is variable to receive deleted data

Post data have been deleted and returned to caller

1 dataOut = pLoc->data

2 if (pPre null)

Deleting first node

1 list. head = pLoc->link

3 else

Deleting other nodes

1 pPre->link = pLoc->link

4 end if

5 list.count = list.count – 1

6 recycle (pLoc)

7 return

end deleteNode