How to Delete from Linked List: Simple Steps and Example

To delete a node from a linked list, you first find the node before the one to delete, then change its next pointer to skip the deleted node. If deleting the head node, update the head pointer to the next node.

Syntax

Deleting a node from a linked list involves these steps:

• Find the node just before the node to delete.
• Change its next pointer to point to the node after the one being deleted.
• If deleting the first node (head), update the head pointer to the next node.

c

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

    // If head node itself holds the key to be deleted
    if (temp != NULL && temp->data == key) {
        *head_ref = temp->next; // Change 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 delete a node with a specific value from a singly linked list in C. It demonstrates deleting the head node and a middle node.

c

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

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

// Function to delete a node by key
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);
}

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

// Function to push a new node at the beginning
void push(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;
}

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

    push(&head, 3);
    push(&head, 2);
    push(&head, 1);

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

    deleteNode(&head, 1); // Delete head
    printf("After deleting 1: ");
    printList(head);

    deleteNode(&head, 3); // Delete last node
    printf("After deleting 3: ");
    printList(head);

    return 0;
}

Output

Original list: 1 -> 2 -> 3 -> NULL
After deleting 1: 2 -> 3 -> NULL
After deleting 3: 2 -> NULL

Common Pitfalls

Common mistakes when deleting from a linked list include:

• Not handling deletion of the head node properly, which can cause the list to lose its starting point.
• Forgetting to update the next pointer of the previous node, leaving the list broken.
• Trying to delete a node that does not exist, which should be safely handled.
• Not freeing the memory of the deleted node, causing memory leaks.

c

/* Wrong way: Not updating head when deleting first node */
void wrongDelete(Node* head, int key) {
    Node* temp = head;
    Node* prev = NULL;
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }
    if (temp == NULL) return;
    if (prev == NULL) {
        // This means head node is to be deleted but head pointer is not updated
        return; // or handle error
    }
    prev->next = temp->next; // Fails if deleting head (prev is NULL)
    free(temp);
}

/* Right way: Use pointer to head pointer */
void rightDelete(Node** head_ref, int key) {
    Node* temp = *head_ref;
    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);
}

Key Takeaways

Always update the head pointer when deleting the first node.

Change the previous node's next pointer to skip the deleted node.

Check if the node to delete exists before attempting deletion.

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

Handle edge cases like empty lists or single-node lists carefully.