Delete Node by Value in DSA C++ - Execution Trace

Concept Flow - Delete Node by Value

Start at head

↓

Check if head is null

|Yes↓

Stop

No↓

Check if head value == target

|Yes↓

Delete head, move head to next

No↓

Traverse list to find node before target

↓

If next node value == target

|Yes↓

Delete next node by linking current to next's next

↓

Stop

No↓

Move to next node

↩Back to Traverse

Start from the head node, check if it matches the value to delete. If yes, remove it by moving head. Otherwise, traverse the list to find the node before the target and remove the target by changing links.

Execution Sample

DSA C++

struct Node {
  int val;
  Node* next;
};

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

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

Execution Table

Step	Current Node Value	Condition	Action	List State
1	10 (head)	head != null	head->val == 5? No → curr = head	10 -> 5 -> 20 -> 30 -> null
2	10	curr->next != null && curr->next->val != 5?	No (5 == 5) → stay at curr=10	10 -> 5 -> 20 -> 30 -> null
3	10	curr->next != null?	Yes → curr->next = curr->next->next (skip 5)	10 -> 20 -> 30 -> null
4	10	Stop	Function ends	10 -> 20 -> 30 -> null

💡 Node with value 5 found and deleted; traversal stops.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
head	10	10	10	10	10
curr	null	10	10	10	10
list	10->5->20->30->null	10->5->20->30->null	10->5->20->30->null	10->20->30->null	10->20->30->null

Key Moments - 3 Insights

Why do we check if the head node contains the target value separately?

Because deleting the head node requires updating the head pointer itself, not just changing links between nodes. This is shown in execution_table step 1 and 3 where head is reassigned.

What happens if the target value is not found in the list?

The traversal continues until curr->next is null, then no deletion occurs and the list remains unchanged. This is implied by the while loop condition in the code.

Why do we check curr->next->val instead of curr->val in the loop?

Because we need to stop at the node before the target to change its next pointer and remove the target node. This is shown in the traversal logic in the code and execution_table step 2.

Visual Quiz - 3 Questions

Look at the execution_table, what is the list state after step 3?

A 10 -> 5 -> 20 -> 30 -> null

B 10 -> 20 -> 30 -> null

C 5 -> 20 -> 30 -> null

D 10 -> 30 -> null

💡 Hint

Check the 'List State' column in execution_table row for step 3.

At which step does the node with value 5 get deleted?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Action' column in execution_table to find when deletion happens.

If the target value was 10 instead of 5, what would happen at step 1?

A Head node would be deleted and head moves to next node

B Traversal would start to find node before 10

C No deletion occurs because 10 is head

D List becomes empty immediately

💡 Hint

Refer to the code and key_moments about deleting the head node.

Concept Snapshot

Delete Node by Value in Linked List:
- Check if list is empty (head == null)
- If head value matches target, move head to next node
- Else traverse to find node before target
- Change next pointer to skip target node
- Stops after first deletion
- Handles head deletion separately

Full Transcript

This visual trace shows how to delete a node by value in a singly linked list. We start at the head node and check if it is null. If the head node's value matches the target, we delete it by moving the head pointer to the next node. Otherwise, we traverse the list to find the node before the target node. Once found, we change its next pointer to skip the target node, effectively deleting it. The execution table shows each step with current node, condition checks, actions, and the list state after changes. Variable tracker shows how head and current pointers change. Key moments clarify why head deletion is special and how traversal works. The quiz tests understanding of list state changes and deletion steps. This method deletes only the first occurrence of the target value.

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