Deletion in a Linked List | C Program

Singly linked list Deletion

In the singly linked list we can delete the node in the following ways –

Deletion Time Complexity (AVG)Θ(1)
Deletion Time Complexity (Worst)O(1)
Space ComplexityO(1)

When we delete the node in the linked list then there are three ways to delete the node as follows.

  • Deletion at beginning
  • Deletion at middle
  • Deletion at last

Deletion operation is easier in the singly linked list.

Efficient memory utilization,i.e no need to pre-allocate memory.

Linear data like a stack, a queue can be easily executed using linked list.

deletion in linked list

Deletion at beginning

So in this diagram Node, A  had been deleted, and after delete, the node will be shown in the diagram.

Algorithm

  • Assign next node in a linked list as the new head
  • free previous head
delete at beginning

Deletion at middle

Algorithm

  • Search the Node to be deleted and call it temp
  • Store previous node call is as previous
  • Assign previous->next to temp->next
  • Free(temp)
Deletion at middle

Deletion at last

  • Search the Node to be deleted and call it temp
  • Store previous node call is as previous
  • Assign previous->next to temp->next
  • In this case, the temp->next will be Null so no difference from deletion at middle
  • Free(temp)
deletion at the end

Code of deletion in a linked list (For a Value)

Following code takes care of all the 3 cases above i.e. deletion at the start, mid and end for a value in a linked list

Run

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

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

void delete(struct Node** head, int delVal)
{
    struct Node* temp = *head;
    struct Node* previous;

    //Case when there is only 1 node in the list
    if(temp->next==NULL)
    {
        *head = NULL;
        free(temp);
        printf("Value %d, deleted \n",delVal);
        return;
    }
    //if the head node itself needs to be deleted
    if(temp!=NULL && temp->data==delVal)
    {
        //Case 1 head becomes 30
        *head = temp->next; //changing head to next in the list
         
        printf("Value %d, deleted \n",delVal);
        //case 1: 22 deleted and freed
        free(temp);
        return;
    }

    //run until we find the value to be deleted in the list
    while (temp != NULL && temp->data != delVal) 
    { 
        //store previous link node as we need to change its next val
        previous = temp; 
        temp = temp->next; 
    }

    //if value is not present then
    //temp will have traversed to last node NULL
    if(temp==NULL)
    {
        printf("Value not found\n");
        return;
    }

    // Case 2: (24)->next = 16 (as 20->next = 16) 
    // Case 3: (16)->next = NULL (as 12->next = NULL)
    previous->next = temp->next;
    free(temp);
    
    //case 2: 20 deleted and freed
    //case 3: 12 deleted and freed
    printf("Value %d, deleted \n",delVal);
}

void display(struct Node* node){

    //as linked list will end when Node is Null
    while(node!=NULL)
    {
        printf("%d ",node->data);
        node = node->next;
    }
    printf("\n");
}

int main()
{
    //creating 4 pointers of type struct Node
    //So these can point to address of struct type variable
    struct Node* head = NULL; 
    struct Node* node2 = NULL; 
    struct Node* node3 = NULL; 
    struct Node* node4 = NULL;
    struct Node* node5 = NULL;
    struct Node* node6 = NULL;

    // allocate 3 nodes in the heap 
    head =  (struct Node*)malloc(sizeof(struct Node)); 
    node2 = (struct Node*)malloc(sizeof(struct Node)); 
    node3 = (struct Node*)malloc(sizeof(struct Node)); 
    node4 = (struct Node*)malloc(sizeof(struct Node)); 
    node5 = (struct Node*)malloc(sizeof(struct Node));
    node6 = (struct Node*)malloc(sizeof(struct Node));

   
    head->data  = 22; // data set for head node 
    head->next  = node2; // next pointer assigned to address of node2 

    node2->data = 30; 
    node2->next = node3; 

    node3->data = 24;
    node3->next = node4; 

    node4->data = 20;
    node4->next = node5; 
   
    node5->data = 16;
    node5->next = node6;

    node6->data = 12;
    node6->next = NULL;

    /*No need for & i.e. address as we do not
    need to change head address
    */
    printf("Linked List Before Operations : "); 
    display(head);

    //deleting first occurance of a value in linked list
    delete(&head,22);
    delete(&head,20);
    delete(&head,12);
  
    printf("Linked List After Operations : ");

    display(head); 

    return 0; 
}

Output

Linked List Before Operations : 22 30 24 20 16 12 
Value 22, deleted
Value 20, deleted
Value 12, deleted
Linked List After Operations : 30 24 16

Code for deletion in a linked list (At Position)

Run

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

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

int calcSize(struct Node* node){
    int size=0;

    while(node!=NULL){
        node = node->next;
        size++;
    }
    return size;
}

void delete(struct Node** head, int pos)
{
    struct Node* temp = *head;
    struct Node* previous;

    //if the head node itself needs to be deleted
    int size = calcSize(*head);

    if(pos<1 || pos>size){
        printf("Enter valid position\n");

        return;
    }

    if(pos==1){
        //Case 1 head becomes 30
        *head = temp->next; //changing head to next in the list
        printf("Value %d, deleted \n",temp->data);

        //case 1: 22 deleted and freed
        free(temp);
        return;
    }

    //run until we find the value to be deleted in the list
    while (--pos) 
    {
        //store previous link node as we need to change its next val
        previous = temp; 
        temp = temp->next; 
    }


    // Case 2: (24)->next = 16 (as 20->next = 16) 
    // Case 3: (16)->next = NULL (as 12->next = NULL)
    previous->next = temp->next;
    printf("Value %d, deleted \n",temp->data);

    free(temp);
    //case 2: 20 deleted and freed
    //case 3: 12 deleted and freed
}

void display(struct Node* node){

    //as linked list will end when Node is Null
    while(node!=NULL)
    {
        printf("%d ",node->data);
        node = node->next;
    }
    printf("\n\n");
}

int main()
{
    //creating 4 pointers of type struct Node
    //So these can point to address of struct type variable
    struct Node* head = NULL; 
    struct Node* node2 = NULL; 
    struct Node* node3 = NULL; 
    struct Node* node4 = NULL;
    struct Node* node5 = NULL;
    struct Node* node6 = NULL;

    // allocate 3 nodes in the heap 
    head =  (struct Node*)malloc(sizeof(struct Node)); 
    node2 = (struct Node*)malloc(sizeof(struct Node)); 
    node3 = (struct Node*)malloc(sizeof(struct Node)); 
    node4 = (struct Node*)malloc(sizeof(struct Node)); 
    node5 = (struct Node*)malloc(sizeof(struct Node));
    node6 = (struct Node*)malloc(sizeof(struct Node));

   
    head->data  = 22; // data set for head node 
    head->next  = node2; // next pointer assigned to address of node2 

    node2->data = 30; 
    node2->next = node3; 

    node3->data = 24;
    node3->next = node4; 

    node4->data = 20;
    node4->next = node5; 
   
    node5->data = 16;
    node5->next = node6;

    node6->data = 12;
    node6->next = NULL;

    /*No need for & i.e. address as we do not
    need to change head address
    */
    printf("Linked List Before Operations : "); 
    display(head);

    //deleting first occurance of a value in linked list
    delete(&head,1);
    delete(&head,3);
    delete(&head,4);
    
    printf("Linked List After Operations : ");
    display(head);

    delete(&head,-2); // not valid as pos negative
    delete(&head,10); // not valid as breaches size of Linked List
    printf("Linked List After Operations : ");
    display(head);

    return 0; 
}

Output

Linked List Before Operations: 22 30 24 20 16 12

Value 22, deleted
Value 20, deleted
Value 12, deleted
Linked List After Operations: 30 24 16

Enter valid position
Enter valid position
Linked List After Operations: 30 24 16
Deletion in singly Linked List in c meme