Deletion in a Linked List | C Program
July 27, 2020
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 Complexity | O[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 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
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 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]
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#include
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 12Value 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#include
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[possize]{
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;
}
Login/Signup to comment