Deleting a Node from a Linked List

We will consider two cases and then see how deletion is done in each case.

  • Case 1: The first node is deleted.
  • Case 2: The last node is deleted.

Deleting the First Node from a Linked List

To delete a node from the beginning of the list, then the following changes will be done in the linked list

Step 1:  check if the linked list exists or not.

If Head = NULL, then there are no nodes in the list and the control is transferred to the last statement of the algorithm. (UNDERFLOW)

Step 2: However, if there are nodes in the linked list, A pointer variable PTR is set to point to the first node of the list. (i.e. initialize PTR with Head that stores the address of the first node )

Step 3: Head is made to point to the next node in sequence

Step 4: Finally, the memory occupied by the node pointed by PTR (initially the first node of the list) is freed and returned to the free pool.

Main logic

Deleting the Last Node from a Linked List

Following steps will be required

Step 1:  check if the linked list exists or not.

If Head = NULL, then there are no nodes in the list and the control is transferred to the last statement of the algorithm. (UNDERFLOW)

Step 2: take a pointer variable PTR and initialize it with head. That is, PTR now points to the first node of the linked list.

Step 3: take another pointer variable PREPTR, In the while loop, we take another pointer variable PREPTR such that it always points to one node before the PTR.

Once we reach the last node and the second last node, we set the NEXT pointer of the second last node to NULL, so that it now becomes the (new) last node of the linked list. The memory of the previous last node is freed and returned back to the free pool.

UNDERFLOW.

A condition that occurs when we try to delete a node from an empty linked list

This happens when Head = NULL or when there are no more nodes to delete.

Note that when we delete a node from a linked list, we actually have to free the memory occupied by that node. The memory is returned to the free pool so that it can be used to store other programs and data.