Delete all occurrences of a given key in a doubly linked list | GFG Practice

Given a doubly linked list and a key, delete all occurrences of the given key from the doubly linked list.

Here’s the [Problem Link] to begin with.

Example1:

Input: 
2<->2<->10<->8<->4<->2<->5<->2
2
Output: 
10<->8<->4<->5
Explanation: 
All Occurences of 2 have been deleted.

Example2:

Input: 
9<->1<->3<->4<->5<->1<->8<->4
9
Output: 
1<->3<->4<->5<->1<->8<->4
Explanation: 
All Occurences of 9 have been deleted.

Your Task:

Complete the function void deleteAllOccurOfX(struct Node** head_ref, int key), which takes the reference of the head pointer and an integer value key. Delete all occurrences of the key from the given DLL.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:

• 1<=Number of Nodes<=10⁵
• 0<=Node Value <=10⁹

Solution: Traversal and Deletion Approach

Intuition

Think of this like removing all instances of a specific word from a sentence written on sticky notes connected to each other! Since it’s a doubly linked list, each note (node) is connected to both its previous and next notes. When we find a note with the word we want to remove, we need to carefully disconnect it and reconnect its neighbors to each other. We also need to be careful about updating the head if we’re removing the first note.

Detailed Approach

1. Handle Single Node Case: If there’s only one node and it matches the key, return null
2. Initialize Pointers: Set up temp pointer to traverse and previous pointer to track the previous node
3. Traverse the List: Go through each node and check if its data matches the key
4. Delete Matching Nodes: When found, update the links of previous and next nodes to skip current node
5. Update Head: If we’re deleting the head node, update the new head
6. Continue Traversal: Keep moving forward until we reach the end

Code

class Solution:
    #Function to delete all the occurances of a key from the linked list.
    def deleteAllOccurOfX(self, head, k):
        # Handle special case: single node that matches the key
        if not head.next and head.data == k:
            return None
        
        temp = head          # Pointer to traverse the list
        previous = None      # Pointer to track previous node
        new_head = head      # Keep track of new head
        
        # Traverse through the entire list
        while temp is not None:
            if temp.data == k:  # Found a node to delete
                # Update previous node's next pointer
                if previous:
                    previous.next = temp.next
                
                # Update next node's prev pointer
                if temp.next:
                    temp.next.prev = previous
                
                # Update head if we're deleting the first node
                if temp == new_head:
                    new_head = new_head.next
            
            previous = temp      # Move previous pointer
            temp = temp.next     # Move to next node
        
        return new_head

Code Explanation

This solution traverses the doubly linked list and deletes all nodes that match the given key. The algorithm handles the special case where there’s only one node that matches the key. During traversal, when a matching node is found, it updates the links of the previous and next nodes to skip the current node. The tricky part is properly updating the head pointer when the first node needs to be deleted. However, there’s a subtle issue in this implementation: the previous pointer is updated even when we delete a node, which can lead to incorrect link management in some cases.

Dry Run

Let’s trace through: 1 <-> 2 <-> 3 <-> 2 <-> 4, delete key = 2

Initial Setup:

• temp = 1, previous = None, new_head = 1

Step 1:

• temp.data = 1, not equal to key (2)
• previous = 1, temp = 2

Step 2:

• temp.data = 2, equal to key
• previous.next = temp.next (node 3)
• temp.next.prev = previous (node 3’s prev becomes node 1)
• temp != new_head, so no head change
• Links now: 1 <-> 3 <-> 2 <-> 4 (first 2 is bypassed)
• previous = 2 (deleted node), temp = 3

Step 3:

• temp.data = 3, not equal to key
• previous = 3, temp = 2 (second occurrence)

Step 4:

• temp.data = 2, equal to key
• previous.next = temp.next (node 4)
• temp.next.prev = previous (node 4’s prev becomes node 3)
• temp != new_head, so no head change
• Links now: 1 <-> 3 <-> 4 (second 2 is bypassed)
• previous = 2 (deleted node), temp = 4

Step 5:

• temp.data = 4, not equal to key
• previous = 4, temp = None

Result: 1 <-> 3 <-> 4

Time and Space Complexity

• Time Complexity: O(n) – We traverse the entire list once
• Space Complexity: O(1) – We only use a few pointer variables

Simplifying It

This approach is like going through a chain of connected items and removing all items of a specific type. Since each item is connected to both its neighbors, when we remove an item, we need to make sure its neighbors are properly connected to each other. We also need to remember to update our starting point if we remove the first item in the chain.

Important Note

While this solution works for most cases, there’s a subtle issue with the pointer management. The previous pointer is updated even when we delete a node, which can potentially cause issues in edge cases. A more robust approach would be to only update the previous pointer when we don’t delete the current node.

Summary

This solution demonstrates the key concepts of doubly linked list manipulation, managing both forward and backward links when deleting nodes. The main challenge is properly handling the pointer updates and edge cases like deleting the head node or all nodes in the list.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.