Deleting a node from a linked list involves removing an element from various positions within the list. This process modifies the list structure by adjusting node references to maintain the integrity of the linked list.
For all the scenarios discussed in this article, linked list node is represented with the below structure:
And this is how the linked list is created before the deletion operation:
Note: If the language you are using does not have garbage collection (C/C++ for example), the memory used by node which is removed from the linked list has to be deallocated manually. In order to keep this article simple, the memory deallocation part is skipped.
Deletion at the Beginning
Deleting a node from the beginning of a linked list involves updating the head to point to it’s next node. Here’s the code snippet:
If there’s only one node in the list, we reset the tail to indicate that there is no tail node after deletion.
Deletion at the End
Unlike the scenario with insertion of a new node at the end of linked list, deletion of the last element requires traversing till last but one element and then deleting the node after it. Here’s the code snipped for deleting last node in a linked list:
The first while loop traverses the linked list until current pointer reaches the end of linked list. prev will point to the node before the tail node. If prev is None, it means that there is only one node in the linked list and the else condition handles it by setting both head and tail of the linked list to None.
Deletion after a Specific Node
Let’s say there are three nodes A->B->C in a linked list in that sequence. And we need to delete the next node after node A. In order to achieve this, we need to retrive the node pointed by node to be deleted (B), which is C, and then updateA node’s to point to C. Here’s a code snippet which does that:
For the example discussed, prev_node variable will point to node A, node_to_delete will point to node B. Before deletion, prev_node.next will point to node B. But after the statement prev_node.next = node_to_delete.next, node C is set as the next node to node A and so the linked list finally becomes A->C.
Deletion at a Specific Position
Deleting a node at a specific position involves traversing the list to the (position-1)th node and then performing deletion similar to what we did for deleting a specific node in the linked list. Here’s the code snippet: