How to Delete a Node from Linked List in C: Simple Guide

To delete a node from a linked list in C, you first find the node to remove, then adjust the pointers of the previous node to skip the deleted node, and finally free the memory of the removed node using free(). This ensures the list stays connected and no memory leaks occur.

Syntax

Here is the basic syntax to delete a node from a singly linked list in C:

• struct Node: Defines the linked list node structure.
• head: Pointer to the first node of the list.
• key: The value of the node to delete.
• temp and prev: Temporary pointers to traverse and track nodes.
• free(): Frees the memory of the deleted node.

c

void deleteNode(struct Node** head_ref, int key) {
    struct Node* temp = *head_ref;
    struct Node* prev = NULL;

    // If head node itself holds the key to be deleted
    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next; // Changed head
        free(temp);             // free old head
        return;
    }

    // Search for the key to be deleted, keep track of previous node
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    // If key was not present in linked list
    if (temp == NULL) return;

    // Unlink the node from linked list
    prev->next = temp->next;

    free(temp); // Free memory
}

Example

This example shows how to create a linked list, delete a node with a specific value, and print the list before and after deletion.

c

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

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

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

void deleteNode(struct Node** head_ref, int key) {
    struct Node* temp = *head_ref;
    struct Node* prev = NULL;

    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

    if (temp == NULL) return;

    prev->next = temp->next;
    free(temp);
}

int main() {
    struct Node* head = malloc(sizeof(struct Node));
    struct Node* second = malloc(sizeof(struct Node));
    struct Node* third = malloc(sizeof(struct Node));

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = NULL;

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

    deleteNode(&head, 2);

    printf("List after deleting 2: ");
    printList(head);

    // Free remaining nodes
    deleteNode(&head, 1);
    deleteNode(&head, 3);

    return 0;
}

Output

Original list: 1 -> 2 -> 3 -> NULL
List after deleting 2: 1 -> 3 -> NULL

Common Pitfalls

Common mistakes when deleting a node from a linked list include:

• Not handling deletion of the head node properly.
• Forgetting to update the previous node's next pointer.
• Not freeing the memory of the deleted node, causing memory leaks.
• Trying to delete a node that does not exist without checking.

Always check if the list is empty or if the node to delete is the first node.

c

/* Wrong way: Not updating previous node or freeing memory */
void wrongDeleteNode(struct Node** head_ref, int key) {
    struct Node* temp = *head_ref;

    while (temp != NULL && temp->data != key) {
        temp = temp->next;
    }

    if (temp == NULL) return; // Node not found

    // This does not unlink the node or free memory
}

/* Correct way: Use previous pointer and free memory as shown in the Syntax section */

Quick Reference

• Always check if the list is empty before deleting.
• Handle the case when the node to delete is the head.
• Traverse the list with two pointers: current and previous.
• Update previous node's next to skip the deleted node.
• Free the deleted node's memory with free().

Key Takeaways

Always handle deletion of the head node separately to update the head pointer.

Use two pointers to find and unlink the node to delete safely.

Free the memory of the deleted node to avoid memory leaks.

Check if the node to delete exists before attempting to remove it.

Update the previous node's next pointer to maintain list integrity.