Delete Node by Value in DSA C++

Mental Model

To remove a node with a specific value, find it by moving through the list, then change the previous node to skip it.

Analogy: Imagine a chain of paper clips linked together. To remove one clip, you unhook it from the one before it, so the chain stays connected without that clip.

head -> 1 -> 2 -> 3 -> 4 -> null

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4, delete value 3

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

Step 1: start at head node with value 1

head -> [curr->1] -> 2 -> 3 -> 4 -> null

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

Step 2: move curr to next node with value 2

head -> 1 -> [curr->2] -> 3 -> 4 -> null

Why: Value 1 is not target, so move forward

Step 3: move curr to next node with value 3

head -> 1 -> 2 -> [curr->3] -> 4 -> null

Why: Found the node with value 3 to delete

Step 4: change previous node's next to skip node 3 and point to node 4

head -> 1 -> 2 -> 4 -> null

Why: Removing node 3 by linking node 2 directly to node 4

Result:

head -> 1 -> 2 -> 4 -> null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

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

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

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

    void deleteByValue(int val) {
        if (!head) return; // empty list
        if (head->data == val) {
            Node* temp = head;
            head = head->next; // remove head
            delete temp;
            return;
        }
        Node* curr = head;
        while (curr->next && curr->next->data != val) {
            curr = curr->next; // advance to node before target
        }
        if (curr->next) {
            Node* temp = curr->next;
            curr->next = curr->next->next; // skip target node
            delete temp;
        }
    }

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

int main() {
    LinkedList list;
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(4);
    list.deleteByValue(3);
    list.printList();
    return 0;
}

if (!head) return; // empty list

handle empty list case to avoid errors

if (head->data == val) { Node* temp = head; head = head->next; // remove head delete temp; return; }

remove head node if it matches the value

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

find node before the one to delete

if (curr->next) { Node* temp = curr->next; curr->next = curr->next->next; // skip target node delete temp; }

unlink and delete the target node

Output

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 regardless of list size

vs Alternative: Compared to rebuilding the list without the value, this method removes the node in one pass without extra space

Edge Cases

empty list

function returns immediately without error

DSA C++

if (!head) return; // empty list

value is at head node

head is updated to next node, old head deleted

DSA C++

if (head->data == val) { ... }

value not found in list

list remains unchanged, no deletion

DSA C++

if (curr->next) { ... }

When to Use This Pattern

When asked to remove a node by value in a linked list, look for traversal to find the node and pointer update to unlink it.

Common Mistakes

Mistake: Not handling deletion of the head node separately
Fix: Add a check for head node value before traversal

Mistake: Not checking if next node exists before accessing its data
Fix: Use condition curr->next && curr->next->data != val in loop

Summary

Deletes the first node with a given value from a singly linked list.

Use when you need to remove a specific value from a linked list without rebuilding it.

The key is to find the node before the target and change its next pointer to skip the target node.

Practice

1. What is the main purpose of the Delete Node by Value operation in a singly linked list?

easy

A. Reverse the entire linked list

B. Add a new node with the given value at the end of the list

C. Remove the first node that contains the given value from the list

D. Find the position of a node with the given value

Solution

1. Step 1: Understand the operation's goal

   The operation aims to remove a node that matches a specific value from the linked list.

2. Step 2: Identify the correct description

   Removing the first node with the given value matches Remove the first node that contains the given value from the list, while others describe different operations.

3. Final Answer:

   Remove the first node that contains the given value from the list -> Option C

4. Quick Check:

   Delete node by value means removing matching node [OK]

Hint: Deleting means removing matching node, not adding or searching [OK]

Common Mistakes:

• Confusing delete with add or search operations
• Thinking it reverses the list
• Assuming it deletes all nodes with the value

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

easy

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

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

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

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

Solution

1. Step 1: Check parameter order and return type

   The function should take the head pointer first and the value to delete second, returning void since it modifies the list.

2. Step 2: Match with options

   void deleteNode(Node* head, int val) { /* code */ } matches the correct parameter order and return type. Others have wrong order or return types.

3. Final Answer:

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

4. Quick Check:

   Head pointer first, value second, void return [OK]

Hint: Function deletes node, so return type is void and head pointer first [OK]

Common Mistakes:

• Swapping parameter order
• Using wrong return type
• Returning Node instead of void

3. What will be the linked list after deleting the node with value 3 from the list: 1 -> 3 -> 5 -> 3 -> 7 -> null?

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

medium

A. 1 -> 5 -> 3 -> 7 -> null

B. 1 -> 3 -> 5 -> 7 -> null

C. 1 -> 5 -> 7 -> null

D. 3 -> 5 -> 3 -> 7 -> null

Solution

1. Step 1: Check if head node has value 3

   Head node is 1, not 3, so skip first if block.

2. Step 2: Traverse to find first node with value 3

   Loop stops at node before first 3 (which is node with value 1). Then deletes first 3 node.

3. Step 3: Update links after deletion

   After deletion, list becomes 1 -> 5 -> 3 -> 7 -> null.

4. Final Answer:

   1 -> 5 -> 3 -> 7 -> null -> Option A

5. Quick Check:

   First 3 deleted, rest unchanged [OK]

Hint: Delete only first matching node, update links carefully [OK]

Common Mistakes:

• Deleting all nodes with value 3
• Deleting wrong node (head vs next)
• Not updating links correctly

4. Identify the bug in the following code snippet for deleting a node by value from a singly linked list:

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

medium

A. The code deletes all nodes with the value instead of first only

B. The head pointer is passed by value, so changes to head are lost

C. The loop condition is incorrect and causes infinite loop

D. The code does not delete the node properly, causing memory leak

Solution

1. Step 1: Analyze head pointer parameter

   Head is passed by value, so changing head inside function does not affect original list.

2. Step 2: Understand impact on deleting head node

   Deleting head node updates local head only, original list head remains unchanged, causing bug.

3. Final Answer:

   The head pointer is passed by value, so changes to head are lost -> Option B

4. Quick Check:

   Pass head by reference to update original list [OK]

Hint: Pass head by reference to delete head node correctly [OK]

Common Mistakes:

• Not passing head by reference
• Assuming head changes reflect outside function
• Ignoring memory leaks

5. Given a singly linked list with possible duplicate values, how would you modify the deleteNode function to delete all nodes with a given value instead of just the first one? Choose the best approach.

hard

A. Use a loop to traverse the list and delete every node matching the value, updating links each time

B. Call the existing deleteNode function repeatedly until no node with the value remains

C. Only delete the head node if it matches, ignore others

D. Reverse the list first, then delete the first matching node

Solution

1. Step 1: Understand requirement to delete all matching nodes

   We must traverse entire list and remove every node with the given value.

2. Step 2: Choose approach that deletes all nodes in one pass

   Use a loop to traverse the list and delete every node matching the value, updating links each time uses a loop to check and delete nodes as we go, updating links properly.

3. Step 3: Evaluate other options

   Call the existing deleteNode function repeatedly until no node with the value remains is inefficient and error-prone; C and D do not delete all nodes.

4. Final Answer:

   Use a loop to traverse the list and delete every node matching the value, updating links each time -> Option A

5. Quick Check:

   Loop and delete all matching nodes in one traversal [OK]

Hint: Traverse once, delete all matches by updating links carefully [OK]

Common Mistakes:

• Deleting only first occurrence
• Calling delete repeatedly without updating head
• Ignoring link updates after deletion