Delete by Value in Doubly Linked List in DSA C++

Mental Model

We find the node with the given value and remove it by linking its neighbors directly to each other.

Analogy: Imagine a train with cars linked front and back. Removing a car means connecting the previous car directly to the next car, skipping the removed one.

null ← 1 ↔ 2 ↔ 3 ↔ 4 -> null
           ↑

Dry Run Walkthrough

Input: list: 1 ↔ 2 ↔ 3 ↔ 4, delete value 3

Goal: Remove the node with value 3 and keep the list connected

Step 1: start at head node with value 1

null ← [1] ↔ 2 ↔ 3 ↔ 4 -> null

Why: We begin searching from the start to find the node to delete

Step 2: move to next node with value 2

null ← 1 ↔ [2] ↔ 3 ↔ 4 -> null

Why: Value 2 is not 3, so continue searching

Step 3: move to next node with value 3

null ← 1 ↔ 2 ↔ [3] ↔ 4 -> null

Why: Found the node with value 3 to delete

Step 4: link node 2's next to node 4 and node 4's prev to node 2, removing node 3

null ← 1 ↔ 2 ↔ 4 -> null

Why: By skipping node 3, we remove it and keep the list connected

Result:

null ← 1 ↔ 2 ↔ 4 -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* prev;
    Node* next;
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

class DoublyLinkedList {
public:
    Node* head;
    DoublyLinkedList() : head(nullptr) {}

    void append(int val) {
        Node* newNode = new Node(val);
        if (!head) {
            head = newNode;
            return;
        }
        Node* curr = head;
        while (curr->next) {
            curr = curr->next;
        }
        curr->next = newNode;
        newNode->prev = curr;
    }

    void deleteByValue(int val) {
        Node* curr = head;
        while (curr && curr->data != val) {
            curr = curr->next;  // advance curr to find node with val
        }
        if (!curr) return; // value not found, do nothing

        if (curr->prev) {
            curr->prev->next = curr->next;  // link previous node to next
        } else {
            head = curr->next;  // deleting head node
        }
        if (curr->next) {
            curr->next->prev = curr->prev;  // link next node back to previous
        }
        delete curr;  // free memory
    }

    void printList() {
        Node* curr = head;
        while (curr) {
            cout << curr->data;
            if (curr->next) cout << " ↔ ";
            curr = curr->next;
        }
        cout << " -> null" << endl;
    }
};

int main() {
    DoublyLinkedList dll;
    dll.append(1);
    dll.append(2);
    dll.append(3);
    dll.append(4);

    cout << "Original list:" << endl;
    dll.printList();

    dll.deleteByValue(3);

    cout << "After deleting value 3:" << endl;
    dll.printList();

    return 0;
}

while (curr && curr->data != val) { curr = curr->next; // advance curr to find node with val }

search for node with the target value

if (!curr) return; // value not found, do nothing

stop if value not found

if (curr->prev) { curr->prev->next = curr->next; // link previous node to next } else { head = curr->next; // deleting head node }

unlink current node from previous or update head if first node

if (curr->next) { curr->next->prev = curr->prev; // link next node back to previous }

unlink current node from next

delete curr; // free memory

remove node from memory

Output

Original list:

1 ↔ 2 ↔ 3 ↔ 4 -> null

After deleting value 3:

1 ↔ 2 ↔ 4 -> null

Complexity Analysis

Time: O(n) because we may need to check each node once to find the value

Space: O(1) because we only use a few pointers and no extra data structures

vs Alternative: Compared to singly linked list deletion, doubly linked list allows direct access to previous node, making unlinking easier without extra traversal

Edge Cases

empty list

deleteByValue does nothing safely

DSA C++

if (!curr) return; // value not found, do nothing

value not in list

no changes to list

DSA C++

if (!curr) return; // value not found, do nothing

deleting head node

head pointer updates to next node

DSA C++

else {
head = curr->next;  // deleting head node
}

deleting tail node

previous node's next pointer set to null

DSA C++

if (curr->next) {
curr->next->prev = curr->prev;  // link next node back to previous
}

When to Use This Pattern

When you need to remove a specific value from a list that links both forward and backward, use the delete by value pattern in doubly linked lists to unlink nodes cleanly.

Common Mistakes

Mistake: Not updating the head pointer when deleting the first node
Fix: Check if the node to delete is head and update head to next node

Mistake: Not updating the prev pointer of the next node
Fix: Always update next node's prev pointer to skip the deleted node

Summary

Deletes a node with a given value by unlinking it from its neighbors in a doubly linked list.

Use when you want to remove a specific value from a doubly linked list efficiently.

The key is to connect the previous and next nodes directly, skipping the node to delete.

Practice

1. What happens when you delete a node by value in a doubly linked list?

easy

A. All nodes are deleted regardless of value.

B. The node with the matching value is removed and links are updated.

C. Only the first node is deleted without checking value.

D. The list is reversed instead of deleting.

Solution

1. Step 1: Locate the node with the given value

   Traverse the list from head to tail to find the node whose data matches the value to delete.

2. Step 2: Update links to remove the node

   Adjust the previous node's next pointer and the next node's previous pointer to bypass the node to be deleted.

3. Final Answer:

   The node with the matching value is removed and links are updated. -> Option B

4. Quick Check:

   Delete by value removes matching node [OK]

Hint: Find node, update previous and next pointers [OK]

Common Mistakes:

• Not updating both previous and next pointers
• Deleting node without checking value
• Deleting all nodes instead of one

2. Which of the following is the correct syntax to delete a node by value in a doubly linked list in C++?

easy

A. void deleteNode(Node* &head, int val) { /* code */ }

B. void deleteNode(int val) { /* code */ }

C. Node deleteNode(int val) { /* code */ }

D. int deleteNode(Node* head, int val) { /* code */ }

Solution

1. Step 1: Understand parameter passing for head pointer

   Head pointer must be passed by reference to allow modification if the first node is deleted.

2. Step 2: Check function return type

   Deletion functions usually return void as they modify the list in place.

3. Final Answer:

   void deleteNode(Node* &head, int val) { /* code */ } -> Option A

4. Quick Check:

   Pass head by reference and return void [OK]

Hint: Pass head by reference to modify list [OK]

Common Mistakes:

• Passing head by value causing no list update
• Returning Node instead of void
• Missing head pointer parameter

3. What is the output of the following code snippet after deleting value 20 from the doubly linked list?

struct Node {
  int data;
  Node* prev;
  Node* next;
};

// List: 10 <-> 20 <-> 30
// deleteNode(head, 20);
// printList(head);

medium

A. 10 <-> null

B. 10 <-> 20 <-> 30 <-> null

C. 20 <-> 30 <-> null

D. 10 <-> 30 <-> null

Solution

1. Step 1: Identify node to delete

   Node with value 20 is in the middle of the list 10 <-> 20 <-> 30.

2. Step 2: Update links after deletion

   After deleting 20, 10's next points to 30, and 30's prev points to 10.

3. Final Answer:

   10 <-> 30 <-> null -> Option D

4. Quick Check:

   Middle node deleted, links updated [OK]

Hint: Deleting middle node links neighbors directly [OK]

Common Mistakes:

• Not updating previous pointer of next node
• Not updating next pointer of previous node
• Leaving deleted node linked

4. Identify the bug in this delete by value function for doubly linked list:

void deleteNode(Node* &head, int val) {
  Node* temp = head;
  while (temp != nullptr && temp->data != val) {
    temp = temp->next;
  }
  if (temp == nullptr) return;
  if (temp->prev != nullptr) temp->prev->next = temp->next;
  if (temp->next != nullptr) temp->next->prev = temp->prev;
  delete temp;
}

medium

A. Does not check for null head pointer

B. Deletes all nodes with matching value

C. Does not update head if first node is deleted

D. Deletes node without freeing memory

Solution

1. Step 1: Check head update when deleting first node

   If the node to delete is the head, head pointer must be updated to next node.

2. Step 2: Verify code for head update

   Code does not update head pointer when temp->prev is nullptr (first node).

3. Final Answer:

   Does not update head if first node is deleted -> Option C

4. Quick Check:

   Head update missing for first node deletion [OK]

Hint: Update head if deleting first node [OK]

Common Mistakes:

• Forgetting to update head pointer
• Not handling empty list
• Deleting without checking node existence

5. Given a doubly linked list with nodes: 5 <-> 10 <-> 15 <-> 20, what will be the list after deleting value 5 and then value 20?

hard

A. 10 <-> 15 <-> null

B. 5 <-> 10 <-> 15 <-> 20 <-> null

C. 10 <-> 15 <-> 20 <-> null

D. 15 <-> null

Solution

1. Step 1: Delete node with value 5 (head node)

   Update head to 10, set 10's prev to nullptr. List becomes 10 <-> 15 <-> 20.

2. Step 2: Delete node with value 20 (tail node)

   Update 15's next to nullptr. List becomes 10 <-> 15.

3. Final Answer:

   10 <-> 15 <-> null -> Option A

4. Quick Check:

   Deleted head and tail nodes correctly [OK]

Hint: Update head and tail pointers when deleting ends [OK]

Common Mistakes:

• Not updating head when deleting first node
• Not updating tail when deleting last node
• Leaving dangling pointers