Deleting a Node from a Linked List

Welcome to the final lesson in our module on linked lists. In the previous lesson, you learned how to traverse a list to search for a specific value. This is a fundamental skill that serves as the first step for many other linked list operations.

Today, we will tackle one of the most important of those operations: implementing a function to delete a node with a specific value. Deleting a node involves more than just finding it; we must carefully manipulate pointers to remove the node from the chain and then free its memory to prevent memory leaks. This process requires careful handling of several cases, especially when the node to be deleted is at the head of thelist.

1. The Logic of Deletion

At its core, deleting a node from a linked list involves three main steps:

1. Find the node you want to delete.
2. Adjust the next pointer of the previous node to bypass the node being deleted, effectively "unlinking" it from the list.
3. Free the memory occupied by the unlinked node.

The most challenging part is step 2. To change the next pointer of the node before the one we're deleting, we need a way to access it. This leads to a common strategy: as we traverse the list looking for the target node, we keep a pointer to the previous node as well.

The following resource provides a brief, high-level overview of this process.

Let's visualize the "re-linking" process for a node in the middle of the list.

2. Handling the Special Cases

While the general logic seems straightforward, we must handle a few special cases to create a robust function.

Case 1: The Node to Delete is the Head

What if the first node in the list is the one we want to delete? There is no "previous" node to modify. In this situation, the head pointer of the list itself must be updated to point to the second node.

This involves these steps:

1. Create a temporary pointer to store the address of the current head node.
2. Update the list's head pointer to point to the second node (head = head->next).
3. Free the memory of the original head node using the temporary pointer.

Case 2: The List is Empty or the Value is Not Found

Our function should gracefully handle the case where the list is empty (head is NULL) or when a full traversal completes without finding the specified value. In these scenarios, the function simply does nothing and returns.

3. Implementing the Deletion Function in C

Now, let's combine these ideas into a C function. We will build a function deleteNodeByValue that takes two arguments:

• A double pointer to the head of the list, struct node **head_ref. We use a double pointer so the function can modify the original head pointer in the calling function (like main), which is necessary if we delete the first node.
• An integer value representing the data of the node to delete.

The following text resource walks through the construction of a similar function. It uses a slightly different function signature but the logic for handling each case is an excellent guide.

Inspired by that resource, here is a complete C function that handles all the cases we've discussed using the double-pointer convention we've been using in this course.

/*
 * Deletes the first occurrence of a node with the given value.
 * head_ref: A pointer to the head pointer of the list.
 * value: The value of the node to delete.
 */
void deleteNodeByValue(struct node **head_ref, int value) {
    // 1. Handle the empty list case.
    if (*head_ref == NULL) {
        return; // Nothing to delete.
    }

    struct node *temp = *head_ref;

    // 2. Handle the case where the head node itself holds the value.
    if (temp->data == value) {
        *head_ref = temp->next; // Change head
        free(temp);             // Free old head
        return;
    }

    // 3. Search for the node to be deleted, keeping track of the previous node.
    // The resource you read uses a "look-ahead" (current->next->data).
    // Here, we'll use a more explicit two-pointer approach: `previous` and `current`.
    struct node *previous = NULL;
    struct node *current = *head_ref;

    // Traverse the list to find the node
    while (current != NULL && current->data != value) {
        previous = current;
        current = current->next;
    }

    // 4. If the value was not found in the list.
    if (current == NULL) {
        return; // Value not present.
    }

    // 5. Unlink the node from the linked list.
    previous->next = current->next;
    free(current); // Free the memory.
}

This function systematically checks for each case: empty list, head node deletion, and then the general case. The use of previous and current pointers is a classic and robust way to implement list modifications.

4. Your Turn: Practice Deletion

It's time to put this all together. In the exercise below, you will complete a main function to test the deleteNodeByValue function. Your task is to build a list and then call the deletion function to remove elements from the beginning, middle, and end of the list.

Exercise:

1. Copy the deleteNodeByValue function from above into the C code below.
2. In main, after the list is built and printed, add calls to deleteNodeByValue to test the following scenarios:
   • Delete 30 (a middle node).
   • Delete 10 (the tail node).
   • Delete 40 (the head node).
   • Attempt to delete 99 (a node that doesn't exist).
3. Print the list after each deletion to verify that it worked correctly.

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

struct node {
    int data;
    struct node *next;
};

// Function to add a node at the start of the list
void insertAtHead(struct node **head_ref, int new_data) {
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

// Function to print the linked list
void printList(struct node *node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

// TODO: Copy the deleteNodeByValue function here.

int main() {
    struct node *head = NULL;

    // Build the list: 40 -> 30 -> 20 -> 10 -> NULL
    insertAtHead(&head, 10);
    insertAtHead(&head, 20);
    insertAtHead(&head, 30);
    insertAtHead(&head, 40);

    printf("Original List: ");
    printList(head);

    // TODO: Add your calls to deleteNodeByValue and printList here.
    // Test deleting a middle, tail, and head node.

    return 0;
}

Original List: 40 -> 30 -> 20 -> 10 -> NULL
After deleting 30 (middle): 40 -> 20 -> 10 -> NULL
After deleting 10 (tail): 40 -> 20 -> NULL
After deleting 40 (head): 20 -> NULL
After attempting to delete 99: 20 -> NULL

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

struct node {
    int data;
    struct node *next;
};

void insertAtHead(struct node **head_ref, int new_data) {
    struct node* new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

void printList(struct node *node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

void deleteNodeByValue(struct node **head_ref, int value) {
    if (*head_ref == NULL) {
        return;
    }

    struct node *temp = *head_ref;
    if (temp->data == value) {
        *head_ref = temp->next;
        free(temp);
        return;
    }
    
    struct node *previous = NULL;
    struct node *current = *head_ref;
    
    while (current != NULL && current->data != value) {
        previous = current;
        current = current->next;
    }
    
    if (current == NULL) {
        return;
    }
    
    previous->next = current->next;
    free(current);
}

int main() {
    struct node *head = NULL;

    insertAtHead(&head, 10);
    insertAtHead(&head, 20);
    insertAtHead(&head, 30);
    insertAtHead(&head, 40);

    printf("Original List: ");
    printList(head);

    // Delete a middle node
    deleteNodeByValue(&head, 30);
    printf("After deleting 30 (middle): ");
    printList(head);

    // Delete the tail node
    deleteNodeByValue(&head, 10);
    printf("After deleting 10 (tail): ");
    printList(head);

    // Delete the head node
    deleteNodeByValue(&head, 40);
    printf("After deleting 40 (head): ");
    printList(head);

    // Attempt to delete a non-existent node
    deleteNodeByValue(&head, 99);
    printf("After attempting to delete 99: ");
    printList(head);

    return 0;
}

Conclusion

Excellent work! You have now mastered all the fundamental operations on a singly linked list: insertion, traversal, searching, and deletion. Deletion ties all these concepts together, requiring careful pointer manipulation and memory management.

Key Takeaways:

• Deleting a node requires finding it, updating the previous node's next pointer to bypass it, and freeing the node's memory.
• Deleting the head of the list is a special case that requires updating the list's main head pointer. Using a double pointer (**head_ref) is a standard C idiom for allowing a function to modify the caller's head pointer.
• A robust implementation must handle edge cases like an empty list or a value not being found.
• Like searching, deletion has a time complexity of O(n) because in the worst case, you might have to traverse the entire list to find the node.

Preview of the Next Lesson:
This lesson concludes our module on linked lists. You've seen how their dynamic, node-based structure offers flexibility for insertions and deletions compared to static arrays. In the next module, we will venture into non-linear data structures, starting with trees. You will discover new ways of organizing data that can offer significant performance advantages for operations like searching, often breaking the O(n) barrier we've seen with linear structures.