7. Deleting a node from a linked list

One of the basic algorithms needed to maintain the list is DELETE. This is explained by carrying on with the example from the previous page.

But basically the DELETE algorithm adjusts the pointer of the relevant nodes to make sure the list remains in the correct order after the node is removed

Example: Storing an alphabetic list of names in a linked list

The diagram above shows the final form of the linked list. This time the task is to remove a node from the linked list

DELETE ALGORITHM

1. Starting with the first node pointed to by the start pointer
2. Is this the node to be removed?
3. Case 1: The node to be removed is the first one.
   1. Adjust the start pointer to point to the next node
   2. Remove the original node
   3. Mark the memory it used as free once more
   4. Task complete
4. Case 2: The node to be removed is an intermediate one
   1. Examine the next node by using the node pointers to move from node to node until the correct node is identified
   2. Node found
   3. Copy the pointer of the removed node into temporary memory
   4. Remove the node from the list and mark the memory it was using as free once more
   5. Update the previous node's pointer with the address held in temporary memory
   6. Task complete
5. Case 3: It is the last node to be removed
   1. Remove the last node from the list
   2. Mark the prior node with a null pointer
   3. Mark the memory the deleted node used as free once more.
   4. Task complete
6. Case 4: Node cannot be found
   1. Return an error message to the calling code
   2. Task complete