Back to Study Material Data Structures and Algorithms

Linked List Deletion

Deleting a node from a linked list requires carefully adjusting pointers so that the remaining nodes still form a valid chain. The main challenge is that t...

Linked List Deletion

Removing Nodes Safely Without Losing the List's Integrity

Deleting a node from a linked list requires carefully adjusting pointers so that the remaining nodes still form a valid chain. The main challenge is that to remove a node, you typically need access to its predecessor so you can point predecessor.next over the deleted node to the next surviving node.

Deleting the head node is a special case requiring no predecessor traversal: set head to head.next. If the list is doubly linked, set the new head's prev to null. If the list becomes empty after deletion, also set tail to null.

Deleting the tail node in a singly linked list requires traversing to the second-to-last node, setting its next to null, and updating the tail pointer. This is O(n) without a tail pointer and O(n) even with one because you still need the predecessor. In a doubly linked list, tail.prev gives the predecessor directly, so deletion of the tail is O(1): set tail to tail.prev, then tail.next to null.

Deleting a node by value: traverse the list, tracking both current and prev pointers. When you find the node whose data equals the target, set prev.next to current.next. If using a doubly linked list, also set current.next.prev to prev. The traversal is O(n) in the worst case.

Deleting a node given only a pointer to that node (not the predecessor) is a classic problem. In a singly linked list, there is a clever trick if the node to delete is not the tail: copy the data from next into the current node and delete next instead. This avoids needing the predecessor. The trick fails if the node is the tail; in that case, you must traverse from head. In a doubly linked list, the prev pointer provides the predecessor directly in O(1).

After deletion, the deleted node's memory should be freed (in languages with manual memory management) or left for the garbage collector (in managed languages). Forgetting to free nodes in C or C++ causes memory leaks.

Worked example: delete the node with value 30 from a singly linked list [10, 20, 30, 40, 50]. Traverse with prev starting at null and current at head. At current (20), it is less than 30; prev moves to 20, current to 30. Current's data equals target. Set 20.next to 30.next (which is 40). Result: [10, 20, 40, 50]. Node 30 is removed.

Interview tip: when deleting from a linked list in an interview, immediately ask whether you have access to a pointer to the node, to the predecessor, or only to the head. The answer changes your approach significantly.