L18. Delete all occurrences of a Key in DLL

This chapter covers the algorithmic approach to deleting all occurrences of a specific target key within a Doubly Linked List (DLL). We will explore the traversal strategy, pointer adjustment rules for edge cases (such as deleting the head node or tail node), memory management differences between languages, and the time-space complexity analysis.

1. Why Do We Need This? (Problem Statement & Status Quo)

When working with doubly linked lists, data elements can repeat. If an application requires purging all instances of a specific value (the key), manually unlinking nodes one by one while keeping the list structurally intact is a common requirement.

• Input: The head of a Doubly Linked List and a target key value.
• Output: The updated head of the Doubly Linked List with every node containing the key completely removed and memory freed.
• The Challenge: Unlike a singly linked list, a DLL has bidirectional links (prev and next). Removing a node requires carefully updating both the previous node's next pointer and the next node's previous pointer, while safely handling boundary conditions like head deletions or tail deletions.

2. Core Mental Model / Analogy

Real-Life Analogy: Imagine a train where each carriage is connected to both the carriage in front of it and the carriage behind it via physical couplers. If you need to remove every old, defective cargo car (the key) from anywhere in the train—whether it's the very first engine car, a middle car, or the last caboose—you cannot simply unhook it. You must securely walk down the train, disconnect both couplers of the target car, attach the preceding car's front coupler directly to the succeeding car, and then detach and discard the target car. If you remove the lead engine car itself, you must officially designate the second car as the new lead engine.

3. Naive vs. Better Approach

4. Step-by-Step Traversal and Pointer Mechanics

To process the DLL without losing track of the structure, we use a traversal pointer called temp.

1. Initialize temp: Place temp at head. Never alter the head directly unless the head node itself matches the key and must be deleted.
2. Inspect Current Node: Check if temp.data == key.
   • If Match: We must delete the current node.
     • Check if temp == head. If true, update head = head.next.
     • Identify prevNode = temp.prev and nextNode = temp.next.
     • Perform pointer adjustments if prevNode or nextNode exist.
     • Free/delete the memory of temp (crucial in C++).
     • Move temp to nextNode.
   • If No Match: Simply advance temp = temp.next.

5. Pointer Adjustment Rules for Deletion

When a matching node is found, its neighboring nodes must be re-linked. Depending on where the node sits in the DLL, four distinct wiring scenarios emerge:

6. Complete Pseudocode Walkthrough

Below is the robust algorithmic pseudocode implementing all edge cases and boundary checks safely:

Function deleteAllOccurrences(head, key):
    temp = head
    
    While temp is not null:
        If temp.data == key:
            // Check if we are deleting the head node
            If temp == head:
                head = head.next
            
            // Capture neighboring nodes
            nextNode = temp.next
            prevNode = temp.prev
            
            // Link next node's previous pointer backward, if it exists
            If nextNode is not null:
                nextNode.prev = prevNode
                
            // Link previous node's next pointer forward, if it exists
            If prevNode is not null:
                prevNode.next = nextNode
                
            // Free memory (Language specific, e.g., C++)
            free(temp)
            
            // Move temp forward to the saved nextNode
            temp = nextNode
        Else:
            // Value does not match, simply move forward
            temp = temp.next
            
    Return head

7. Language-Specific Considerations & Memory Management

• C / C++: You must explicitly release allocated memory using free() or delete. Failing to do so results in memory leaks, as unlinked nodes remain resident in heap memory.
• Java / Python / JavaScript: Automatic Garbage Collection (GC) handles memory cleanup. Once a node is unlinked from both prev and nextNode references, the garbage collector automatically reclaims the memory.

8. Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$, where $N$ is the number of nodes in the Doubly Linked List. We visit each node exactly once during a single linear traversal.
• Space Complexity: $\mathcal{O}(1)$. No additional data structures or auxiliary memory allocations are used; all deletions and pointer modifications are performed in-place.

Summary and Key Takeaways

• Maintain Head Integrity: Never mutate the head pointer directly with the traversal variable; instead, use a dedicated temp pointer.
• Handle Head Deletions Specially: If temp == head, updating head = head.next ensures the list entry point remains valid.
• Guard Against Null Pointers: Always verify if prevNode and nextNode are non-null before attempting to modify their pointer fields (.next or .prev).
• In-Place Re-linking: Doubly linked lists require updating two directional pointers (prev and next) around the deleted node.
• Memory Management: Always free deleted nodes in languages like C++ to prevent memory leaks.
• Optimal Efficiency: The problem can be solved in a single pass with $\mathcal{O}(N)$ time complexity and $\mathcal{O}(1)$ auxiliary space complexity.