Delete a Node from a Singly Linked List

  • Write a C program to delete a node from a Singly linked list

We have to delete a node from a linked list whose value is given. Node to be deleted may be head node, tail node or any internal node. We have to handle deletion of all three use cases in a single function called "deleteNode". Function "deleteNode" will takes head pointer of a linked list and value of the node to be deleted.

Singly linked list's node structure is as follows: 
struct node {
    int data;
    struct node *next;
}
Algorithm to delete a node from linked list whole value is given.

Let "num" be the value of node to be deleted from linked list.
  • We will use two node pointers "current" and "previous" to keep track of the current and previous node while traversing linked list. current pointer is initialized to head pointer.
  • Check If value of head node is equal to "num". If equal, then set head = current->next; and delete current node. If head->data != num then continue.
  • Traverse linked list from head to tail(keeping track of the previous visited node) and search for a node whose value is "num".
  • If we find a node whose data is "num", then set previous->next = current->next; and delete current node.
  • If after complete traversal of linked list we won't find a node whose data is "num" then return.

C program to delete a node from linked list

#include <stdio.h>
#include <stdlib.h>
 
/* A structure of linked list node */
struct node {
  int data;
  struct node *next;
} *head;

void initialize(){
    head = NULL;
}

/* 
Given a Inserts a node in front of a singly linked list. 
*/
void insert(int num) {
    /* Create a new Linked List node */
    struct node* newNode = (struct node*) malloc(sizeof(struct node));
    newNode->data  = num;
    /* Next pointer of new node will point to head node of linked list  */
    newNode->next = head;
    /* make new node as new head of linked list */
    head = newNode;
    printf("Inserted Element : %d\n", num);
}

void deleteNode(struct node *head, int num) {
    struct node *current = head, *previous;
    /* Input Validation */
    if (head == NULL) { 
       printf("Error : Invalid node pointer !!!\n");       
       return;  
    }
    
    /* If head head node itself contains num, 
    then delete head node and shift head pointer */
    if (current->data == num) {
        head = current->next;   
        free(current);        
        return;
    }
 
    /* Traverse given linked list and search for key. 
    If found, keep a pointer to previous node also. */
    while (current != NULL && current->data != num) {
        previous = current;
        current = current->next;
    }
 
    /* num not found in given Linked list */
    if (current == NULL){
        printf("%d not found in Linked List\n");
        return;
    }
    /* Set next pointer of previous node to 
    next pointer of temp(current node)*/
    previous->next = current->next;

    /* DeAllocate memory of node */
    free(current);
}

/*
Prints a linked list from head node till tail node 
*/
void printLinkedList(struct node *nodePtr) {
  while (nodePtr != NULL) {
     printf("%d", nodePtr->data);
     nodePtr = nodePtr->next;
     if(nodePtr != NULL)
         printf("-->");
  }
}
 
int main() {
    initialize();
    /* Creating a linked List*/
    insert(2);  
    insert(4); 
    insert(5); 
    insert(9);
    printf("\nBefore Deletion\n");
    printLinkedList(head);
    /* Deleting a node from Linked List */
    deleteNode(head, 5);
    /* Deleting head node */
    deleteNode(head, 2);
    printf("\nAfter Deletion\n");
    printLinkedList(head);
    return 0;
}
Output
Inserted Element : 2
Inserted Element : 4
Inserted Element : 5
Inserted Element : 9

Before Deletion
9-->5-->4-->2
After Deletion
9-->4
Posted by
Labels: