# Deletion in a Linked List | C Program

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 ### 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

Run

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

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

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

//Case when there is only 1 node in the list
if(temp->next==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)
{

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)
{
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* node2 = NULL;
struct Node* node3 = NULL;
struct Node* node4 = NULL;
struct Node* node5 = NULL;
struct Node* node6 = NULL;

// allocate 3 nodes in the heap
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));

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
*/
printf("Linked List Before Operations : ");

//deleting first occurance of a value in linked list

printf("Linked List After Operations : ");

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* previous;

//if the head node itself needs to be deleted

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

return;
}

if(pos==1){
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* node2 = NULL;
struct Node* node3 = NULL;
struct Node* node4 = NULL;
struct Node* node5 = NULL;
struct Node* node6 = NULL;

// allocate 3 nodes in the heap
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));

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
*/
printf("Linked List Before Operations : ");

//deleting first occurance of a value in linked list

printf("Linked List After Operations : ");
`Linked List Before Operations: 22 30 24 20 16 12Value 22, deleted Value 20, deleted Value 12, deleted Linked List After Operations: 30 24 16Enter valid positionEnter valid positionLinked List After Operations: 30 24 16` 