Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Deleting from a Doubly Linked List

EASYProblemSolveExternal Links

Description

You are given the head of a doubly linked list and an integer key. Your task is to delete all occurrences of the given key from the list and return the head of the modified doubly linked list.

In a doubly linked list, each node has three components:

  • data — the value stored in the node
  • next — a pointer to the next node (or null if it's the last node)
  • prev — a pointer to the previous node (or null if it's the first node)

When deleting a node, you must correctly update the next and prev pointers of the surrounding nodes so that the doubly linked structure remains intact. You must handle all edge cases:

  • Deleting the head node (no previous node exists)
  • Deleting a middle node (both previous and next nodes exist)
  • Deleting the tail node (no next node exists)
  • Deleting consecutive nodes with the same value
  • All nodes in the list having the same value as the key (entire list gets deleted)

Examples

Example 1

Input: LinkedList = 2 <-> 2 <-> 10 <-> 8 <-> 4 <-> 2 <-> 5 <-> 2, key = 2

Output: 10 <-> 8 <-> 4 <-> 5

Explanation: All nodes with value 2 are removed. The first two nodes (both value 2) are deleted — the head changes to the node with value 10. The node with value 2 between 4 and 5 is also deleted, and the trailing node with value 2 at the end is deleted. Four pointer adjustments happen for each deletion.

Example 2

Input: LinkedList = 9 <-> 1 <-> 3 <-> 4 <-> 5 <-> 1 <-> 8 <-> 4, key = 9

Output: 1 <-> 3 <-> 4 <-> 5 <-> 1 <-> 8 <-> 4

Explanation: Only the head node has value 9. After deleting it, the new head becomes the node with value 1. The new head's prev pointer is set to null since it's now the first node.

Example 3

Input: LinkedList = 5 <-> 5 <-> 5, key = 5

Output: (empty list)

Explanation: Every node has value 5, which matches the key. All nodes are deleted. The function returns null since the list becomes empty.

Constraints

  • 1 ≤ number of nodes ≤ 10^5
  • 0 ≤ node value ≤ 10^9
  • Expected Time Complexity: O(n)
  • Expected Auxiliary Space Complexity: O(1)

Editorial

Single-Pass Traversal with In-Place Deletion

Intuition

To delete all occurrences of a key from a doubly linked list, we simply walk through every node in the list, and whenever we find a node whose value matches the key, we remove it by rewiring the surrounding pointers.

The beauty of a doubly linked list for deletion is that each node already knows both its predecessor and its successor. So when we decide to delete a node, we have all the information we need right there — no need to maintain a separate "previous" pointer as we would in a singly linked list.

Think of it like removing people from a line of people holding hands. Each person holds the hand of the person in front and behind them. To remove someone:

  • The person behind grabs the hand of the person in front (skipping the removed person).
  • The person in front grabs the hand of the person behind (also skipping the removed person).

There are three special cases to handle:

1. Deleting the head: When the first node matches the key, there's no previous node. We simply move the head forward. The new head's prev pointer must be set to null.

2. Deleting the tail: When the last node matches the key, there's no next node. We just set the previous node's next pointer to null.

3. Deleting a middle node: Both neighbors exist. We connect the previous node directly to the next node, bypassing the deleted node entirely.

Since we must check every node (the key could appear anywhere and multiple times), the minimum work required is O(n) — one full traversal. This is already optimal. No data structure or technique can avoid examining each node at least once.

Step-by-Step Explanation

Let's trace through with LinkedList = 2 <-> 2 <-> 10 <-> 8 <-> 4 <-> 2 <-> 5 <-> 2, key = 2:

Step 1: Start at head (node with value 2). It matches the key! Delete it. Move head to the next node (value 2). Set new head's prev = null.

Step 2: Current node is the new head (value 2). It also matches the key! Delete it. Move head to the next node (value 10). Set new head's prev = null.

Step 3: Current node has value 10. Does not match key (2). Move to the next node.

Step 4: Current node has value 8. Does not match key (2). Move to the next node.

Step 5: Current node has value 4. Does not match key (2). Move to the next node.

Step 6: Current node has value 2. It matches the key! This is a middle node. Set prev node (4)'s next → next node (5). Set next node (5)'s prev → prev node (4). Node with value 2 is removed.

Step 7: Current node has value 5. Does not match key (2). Move to the next node.

Step 8: Current node has value 2 (the tail). It matches the key! This is the tail node. Set prev node (5)'s next = null. Node with value 2 is removed.

Result: The list is now 10 <-> 8 <-> 4 <-> 5.

Deleting All Occurrences of Key=2 from a Doubly Linked List — Watch how we traverse the doubly linked list node by node, deleting every node whose value matches the key by rewiring pointers, handling head, middle, and tail deletions.

Algorithm

  1. Start with a pointer curr at the head of the list.
  2. While curr is not null:
    • Save curr.next as nextNode (we need this since we might delete curr).
    • If curr.data == key:
      • Case 1 — Head node: If curr.prev is null (it's the head), move head = curr.next. If the new head exists, set head.prev = null.
      • Case 2 — Tail node: If curr.next is null (it's the tail), set curr.prev.next = null.
      • Case 3 — Middle node: Both neighbors exist. Set curr.prev.next = curr.next and curr.next.prev = curr.prev.
    • Move curr = nextNode to continue traversal.
  3. Return head (which may have changed if the original head was deleted).

Code

class Solution {
public:
    Node* deleteAllOccurOfX(Node* head, int x) {
        Node* curr = head;
        
        while (curr != nullptr) {
            Node* nextNode = curr->next;
            
            if (curr->data == x) {
                // Case 1: Deleting the head node
                if (curr->prev == nullptr) {
                    head = curr->next;
                    if (head != nullptr) {
                        head->prev = nullptr;
                    }
                }
                // Case 2: Deleting the tail node
                else if (curr->next == nullptr) {
                    curr->prev->next = nullptr;
                }
                // Case 3: Deleting a middle node
                else {
                    curr->prev->next = curr->next;
                    curr->next->prev = curr->prev;
                }
                
                delete curr; // Free memory
            }
            
            curr = nextNode;
        }
        
        return head;
    }
};
class Solution:
    def deleteAllOccurOfX(self, head, x):
        curr = head
        
        while curr is not None:
            next_node = curr.next
            
            if curr.data == x:
                # Case 1: Deleting the head node
                if curr.prev is None:
                    head = curr.next
                    if head is not None:
                        head.prev = None
                # Case 2: Deleting the tail node
                elif curr.next is None:
                    curr.prev.next = None
                # Case 3: Deleting a middle node
                else:
                    curr.prev.next = curr.next
                    curr.next.prev = curr.prev
            
            curr = next_node
        
        return head
class Solution {
    Node deleteAllOccurOfX(Node head, int x) {
        Node curr = head;
        
        while (curr != null) {
            Node nextNode = curr.next;
            
            if (curr.data == x) {
                // Case 1: Deleting the head node
                if (curr.prev == null) {
                    head = curr.next;
                    if (head != null) {
                        head.prev = null;
                    }
                }
                // Case 2: Deleting the tail node
                else if (curr.next == null) {
                    curr.prev.next = null;
                }
                // Case 3: Deleting a middle node
                else {
                    curr.prev.next = curr.next;
                    curr.next.prev = curr.prev;
                }
            }
            
            curr = nextNode;
        }
        
        return head;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the entire list exactly once, visiting each of the n nodes exactly one time. At each node, we do O(1) work — either skip it or delete it (pointer rewiring is constant time). This is optimal because we must examine every node to determine whether it matches the key.

Space Complexity: O(1)

We only use a constant number of pointer variables (curr, nextNode) regardless of the input size. No additional data structures are allocated. The deletions are performed in-place by modifying the existing pointers.