Deletion

Deletion in Linked List

Deletion involves re-routing pointers to bypass the target node, then freeing its memory.

3 Deletion Cases

Case 1 — Delete Head O(1)

Before: HEAD -> [10] -> [20] -> [30] -> NULL
After:  HEAD ->         [20] -> [30] -> NULL

Simply move head = head->next and free the old head.

Case 2 — Delete by Value O(N)

Before: HEAD -> [10] -> [20] -> [30] -> NULL
Delete 20
After:  HEAD -> [10] ----------> [30] -> NULL

Traverse keeping a prev pointer. When target found: prev->next = temp->next.

Case 3 — Delete Tail O(N)

Before: HEAD -> [10] -> [20] -> [30] -> NULL
After:  HEAD -> [10] -> [20] -> NULL

Traverse to second-last node, set its next = NULL, free the tail.

⚠️ Always free() / delete the removed node to prevent memory leaks.