C Program to Delete a Node from a Linked List

Introduction

A linked list is a dynamic data structure where each element, called a node, contains a data part and a pointer to the next node. Deleting a node from a linked list involves finding the node, adjusting the pointers of the previous node (if any), and then freeing the memory allocated to the node to be deleted.

Example:

• Input: A linked list with nodes containing [10, 20, 30, 40] and the data value 30 to delete.
• Output: The linked list after deletion will contain [10, 20, 40].

Problem Statement

Create a C program that:

• Creates a singly linked list.
• Deletes a node with a specific value from the linked list.
• Displays the linked list after the deletion.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output functions and dynamic memory allocation.
2. Define the Node Structure: Create a structure for the node containing an integer data part and a pointer to the next node.
3. Implement the Function to Delete a Node: Write a function that deletes a node with a specific value from the linked list.
4. Implement the Function to Display the Linked List: Write a function to traverse and display the elements of the linked list.
5. Create a Main Function: In the main() function, create the linked list, delete a node, and display the list.

C Program to Delete a Node from a Linked List

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

// Step 2: Define the Node Structure
struct Node {
    int data;
    struct Node* next;
};

// Function to delete a node with a specific key
void deleteNode(struct Node** head_ref, int key) {
    struct Node* temp = *head_ref;
    struct Node* prev = NULL;

    // If the 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 the previous node
    while (temp != NULL && temp->data != key) {
        prev = temp;
        temp = temp->next;
    }

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

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

    // Free memory
    free(temp);
}

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

// Function to insert a node at the end of the linked list
void insertAtEnd(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;

    new_node->data = new_data;
    new_node->next = NULL;

    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }

    last->next = new_node;
}

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

    // Insert elements at the end
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    insertAtEnd(&head, 40);

    // Display the linked list before deletion
    printf("Linked List before deletion: ");
    displayList(head);

    // Delete a node
    deleteNode(&head, 30);

    // Display the linked list after deletion
    printf("Linked List after deletion: ");
    displayList(head);

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Step 2: Define the Node Structure

• The Node structure contains two members: an integer data to store the node’s data, and a pointer next to point to the next node in the list.

Function to Delete a Node

• The deleteNode function takes a double pointer to the head of the linked list (head_ref) and the key to be deleted (key).
• It first checks if the head node contains the key to be deleted. If so, it updates the head pointer to point to the next node and frees the old head.
• If the key is not in the head node, the function traverses the linked list to find the node containing the key while keeping track of the previous node (prev).
• Once the node with the key is found, it is unlinked from the list, and its memory is freed.

Function to Display the Linked List

• The displayList function traverses the linked list from the head and prints each node’s data, followed by an arrow (->), until it reaches the end (NULL).

Main Function

• The main function creates a linked list by inserting nodes at the end using the insertAtEnd function.
• It then displays the linked list, deletes a node with the key 30, and displays the list again after deletion.

Output Example

Example Output:

Linked List before deletion: 10 -> 20 -> 30 -> 40 -> NULL
Linked List after deletion: 10 -> 20 -> 40 -> NULL

Conclusion

This C program demonstrates how to delete a node from a linked list. It covers basic concepts such as dynamic memory allocation, pointer manipulation, and linked list traversal, making it a useful example for beginners learning data structures in C programming.