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

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

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

void insert(struct Node** head, int data){

struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

newNode->data = data;
newNode->next = *head;

//changing the new head to this freshly entered node
*head = newNode;
}

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()
{
struct Node* head = NULL;

/*Need & i.e. address as we
need to change head address only needs to traverse
and access items temporarily
*/
insert(&head,12);
insert(&head,16);
insert(&head,20);
insert(&head,24);
insert(&head,30);
insert(&head,22);

/*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)

#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 insert(struct Node** head, int data){

struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));

newNode->data = data;
newNode->next = *head;

//changing the new head to this freshly entered node
*head = newNode;
}

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()
{
struct Node* head = NULL;

/*Need & i.e. address as we
need to change head address only needs to traverse
and access items temporarily
*/
insert(&head,12);
insert(&head,16);
insert(&head,20);
insert(&head,24);
insert(&head,30);
insert(&head,22);


/*No need for & i.e. address as we do not
need to change head address
*/
display(head);

//deleting first occurance of a value in linked list
delete(&head,1);
display(head);

delete(&head,3);
display(head);

delete(&head,4);
display(head);

delete(&head,-2);
delete(&head,10);

return 0;
}
Deletion in singly Linked List in c meme