Delete Node by Value in DSA C++ - Time & Space Complexity

Time Complexity: Delete Node by Value

O(n)

Understanding Time Complexity

We want to know how long it takes to remove a node with a specific value from a linked list.

How does the time needed change as the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void deleteNodeByValue(Node*& head, int value) {
    if (!head) return;
    if (head->data == value) {
        Node* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    Node* current = head;
    while (current->next && current->next->data != value) {
        current = current->next;
    }
    if (current->next) {
        Node* temp = current->next;
        current->next = current->next->next;
        delete temp;
    }
}
    

This code searches for the first node with the given value and removes it from the linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves through the list nodes one by one.
• How many times: Up to n times, where n is the number of nodes in the list.

How Execution Grows With Input

As the list grows, the time to find the node grows roughly in a straight line.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The number of steps grows directly with the list size.

Final Time Complexity

Time Complexity: O(n)

This means the time to delete a node grows linearly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Deleting a node by value always takes constant time because we just remove it."

[OK] Correct: We must first find the node by checking each one, which can take time proportional to the list size.

Interview Connect

Understanding how searching affects deletion time helps you explain linked list operations clearly and confidently.

Self-Check

"What if the list was doubly linked? How would the time complexity for deleting a node by value change?"

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