Delete Node by Value in DSA C

Mental Model

To remove a node with a specific value, find it first, then change the links to skip it.

Analogy: Imagine a chain of paper clips linked together. To remove one clip, you unhook it and connect the clips before and after it directly.

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 first node

Step 2: move curr to next node with value 2

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

Why: Value 1 is not 3, so continue searching

Step 3: move curr to next node with value 3

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

Why: Found node with value 3 to delete

Step 4: change next pointer of node with value 2 to node with value 4, skipping 3

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

Why: By skipping node 3, it is removed from the list

Result:

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

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Create new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Insert node at end
void insertEnd(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    Node* curr = *head;
    while (curr->next != NULL) {
        curr = curr->next;
    }
    curr->next = newNode;
}

// Delete node by value
void deleteNodeByValue(Node** head, int value) {
    if (*head == NULL) return; // empty list

    // If head node holds the value
    if ((*head)->data == value) {
        Node* temp = *head;
        *head = (*head)->next; // move head
        free(temp);
        return;
    }

    Node* curr = *head;
    // Traverse to find node before the one to delete
    while (curr->next != NULL && curr->next->data != value) {
        curr = curr->next; // advance curr
    }

    // If node with value found
    if (curr->next != NULL) {
        Node* temp = curr->next;
        curr->next = curr->next->next; // skip node
        free(temp);
    }
}

// Print list
void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("null\n");
}

int main() {
    Node* head = NULL;
    insertEnd(&head, 1);
    insertEnd(&head, 2);
    insertEnd(&head, 3);
    insertEnd(&head, 4);

    printf("Original list:\n");
    printList(head);

    deleteNodeByValue(&head, 3);

    printf("List after deleting value 3:\n");
    printList(head);

    return 0;
}

if ((*head)->data == value) {

check if head node contains the value to delete

*head = (*head)->next; // move head

remove head by moving head pointer to next node

while (curr->next != NULL && curr->next->data != value) {

traverse list to find node before the one to delete

curr->next = curr->next->next; // skip node

unlink node with value by skipping it in the chain

Output

Original list:

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

List 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 rebuilding the list without the value, this method is faster because it changes links directly without copying nodes

Edge Cases

empty list

function returns immediately without changes

DSA C

if (*head == NULL) return; // empty list

value is at head node

head pointer moves to next node, old head freed

DSA C

if ((*head)->data == value) {

value not found in list

list remains unchanged

DSA C

if (curr->next != NULL) {

When to Use This Pattern

When you need to remove a specific value from a linked list, use the delete-by-value pattern to find and unlink the node efficiently.

Common Mistakes

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

Mistake: Not updating the previous node's next pointer to skip the deleted node
Fix: Set previous node's next to deleted node's next to unlink it

Summary

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

Use when you want to remove a node by its value, not by position.

Remember to handle the head node separately and update links to skip the deleted node.

Practice

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

easy

A. To remove the first node that contains the given value from the list

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

C. To find the position of a node with the given value

D. To reverse the linked list

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 To remove the first node that contains the given value from the list, while others describe different operations.

3. Final Answer:

   To remove the first node that contains the given value from the list -> Option A

4. Quick Check:

   Delete Node by Value = Remove matching node [OK]

Hint: Deleting by value means removing the first matching node [OK]

Common Mistakes:

• Confusing deletion by value with insertion
• Thinking it reverses the list
• Assuming it finds position only

2. Which of the following is the correct way to start deleting a node by value in a singly linked list in C?

easy

A. Reverse the list before deletion

B. Directly free the head pointer without checks

C. Create a new node with the value to delete

D. Set a pointer to the head and check if head's value matches

Solution

1. Step 1: Understand deletion start

   We must check if the head node itself contains the value to delete before moving forward.

2. Step 2: Identify correct approach

   Setting a pointer to head and checking its value is the correct first step; other options are incorrect or irrelevant.

3. Final Answer:

   Set a pointer to the head and check if head's value matches -> Option D

4. Quick Check:

   Start at head to delete by value [OK]

Hint: Always check head node first when deleting by value [OK]

Common Mistakes:

• Freeing head without checking value
• Creating new nodes unnecessarily
• Reversing list before deletion

3. Consider the following linked list: 10 -> 20 -> 30 -> 40 -> NULL. After deleting the node with value 30, what will be the new list?

medium

A. 10 -> 30 -> 40 -> NULL

B. 10 -> 20 -> 40 -> NULL

C. 20 -> 30 -> 40 -> NULL

D. 10 -> 20 -> 30 -> 40 -> NULL

Solution

1. Step 1: Locate node with value 30

   Traverse the list: 10, 20, then 30 is found as the third node.

2. Step 2: Remove node 30 and link previous to next

   Link node with value 20 directly to node with value 40, skipping 30.

3. Final Answer:

   10 -> 20 -> 40 -> NULL -> Option B

4. Quick Check:

   Deleted 30, list skips it [OK]

Hint: Link previous node to next to remove target node [OK]

Common Mistakes:

• Not updating previous node's next pointer
• Deleting wrong node
• Leaving deleted node in list

4. Given this code snippet to delete a node by value, what is the main error?

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

medium

A. prev pointer is never updated

B. The loop condition is incorrect and never runs

C. free(temp) is called before updating pointers, causing invalid access

D. The function does not handle empty list

Solution

1. Step 1: Analyze order of free and pointer update

   The code frees temp before updating prev->next or head, so temp->next access is invalid.

2. Step 2: Identify correct fix

   Pointers must be updated before freeing the node to avoid accessing freed memory.

3. Final Answer:

   free(temp) is called before updating pointers, causing invalid access -> Option C

4. Quick Check:

   Free after pointer update to avoid errors [OK]

Hint: Update pointers before freeing node to avoid invalid access [OK]

Common Mistakes:

• Freeing node before fixing links
• Ignoring NULL list case
• Not updating prev pointer

5. You have a singly linked list: 5 -> 10 -> 15 -> 20 -> 25 -> NULL. Write a function to delete all nodes with value greater than 15. What will be the final list after deletion?

hard

A. 5 -> 10 -> 15 -> NULL

B. 5 -> 10 -> 20 -> 25 -> NULL

C. 15 -> 20 -> 25 -> NULL

D. 5 -> 10 -> 15 -> 20 -> 25 -> NULL

Solution

1. Step 1: Identify nodes with value > 15

   Nodes with values 20 and 25 are greater than 15 and must be deleted.

2. Step 2: Delete nodes and link remaining nodes

   After removing 20 and 25, the list becomes 5 -> 10 -> 15 -> NULL.

3. Final Answer:

   5 -> 10 -> 15 -> NULL -> Option A

4. Quick Check:

   Removed nodes > 15, list ends at 15 [OK]

Hint: Delete nodes by checking value > 15 and relink list [OK]

Common Mistakes:

• Deleting wrong nodes
• Not updating links after deletion
• Assuming only one node deleted