Deletion in a linear linked list, like insertion, can be done in these ways-
- Deletion at the beginning
- Deletion at the end
- Deletion of a given node
- Deletion after a node with given value
- Deletion before a node with given value
- Deletion at a given position
Deletion at the Beginning
When a node has to be deleted at the beginning of the linked list, the original second node becomes the first node. This is done by assigning the address stored in the LINK part of first node to START pointer.
Deletion in a linked list at the End
After deleting node at the end of the linked list, the second last node becomes the last node. This is done by traversing to the end of the Linked List. While traversing, the current node address PTR is SAVE pointer and PTR pointer is updated with PTR->LINK.
At the end of traversal the last node’s address is stored in a pointer PTR and address of second last node in SAVE pointer. LINK part of the second last node is assigned the link part of last node. Since the last node’s LINK part is NULL, when it is assigned to LINK part of last node, it becomes the last node now.
Deletion a node with given value
Deletion of a node with a given value, is done by following these steps –
- Traverse the linked list to locate the element which is to be deleted. Store address of this node in a pointer PTR and its previous node’s address in SAVE pointer.
- Store value of LINK part of the node identified by PTR in LINK part of SAVE node.
Deletion before a node with given value
A node can be deleted before a node with given value by following these steps
- Traverse the linked list to locate the element before which the new node is to be deleted. Store address of its previous node in SAVE pointer and the current node in PTR pointer. Here the DATA part of PTR’s next node (accessing PTR->LINK->DATA) is compared with the given value.
- Address stored in LINK part of the node identified by PTR in assigned to LINK part of SAVE node
Deletion after a node with given value
A node can be deleted after a node with given value by following these steps
- Traverse the linked list to locate the element after which the node is to be deleted. Store address of this node in PTR pointer.
- Store address in LINK part of the next node identified by PTR-> LINK into LINK part of node identified by PTR.
Deletion at a given Position
Deletion in a linked list can done be at a given location. For example you want to delete an element at 5th Location. In this case a counter variable is required that increments with each iteration of traversal process. The traversal end when the counter variable is equal to the position of element to be deleted.
SAVE pointer is used to store the address of previously traversed node. stop when this counter becomes equal to the position of insertion. Update LINK of SAVE node with LINK of PTR (handing over the address of next node to SAVE node)