# 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 Complexity O(1)

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

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

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

## Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

## Checkout list of all the video courses in PrepInsta Prime Subscription

### Singly Linked List

• Introduction to Linked List in Data Structure
• Linked List in – C | C++ | Java
• Singly Linked List in – C | C++ | Java
• Insertion in singly Linked List – C | C++ | Java
• Insertion at beginning in singly Linked List  – C | C++Java
• Insertion at nth position in singly Linked List  – C | C++Java
• Insertion at end in singly Linked List  – C | C++Java
• Deletion in singly Linked List  – C | C++Java
• Deletion from beginning in singly linked list : C | C++ | Java
• Deletion from nth position in singly linked list : C | C++ | Java
• Deletion from end in singly linked list : C | C++ | Java
• Reverse a linked list without changing links between nodes (Data reverse only) – C | C++Java
• Linked List Insertion and Deletion – C | C++Java
• Reverse a linked list by changing links between nodes – C | C++Java
• Linked List insertion in the middle – C | C++Java
• Print reverse of a linked list without actually reversing – C |C++ | Java
• Search an element in a linked list – C | C++Java
• Insertion in a Sorted Linked List – C | C++Java
• Delete alternate nodes of a Linked List – C | C++Java
• Find middle of the linked list – C | C++Java
• Reverse a linked list in groups of given size – C | C++Java
• Find kth node from end of the linked list – C | C++Java
• Append the last n nodes of a linked list to the beginning of the list – C | C++Java
• Check whether linked list is palindrome or not – C | C++Java
• Fold a Linked List – C | C++Java
• Insert at a given position – C | C++Java
• Delete at a given position – C | C++Java

### Singly Linked List

• Introduction to Linked List in Data Structure
Click Here
• Linked List in –
C | C++ | Java
• Singly Linked List in –
C | C++ | Java
• Insertion in singly Linked List –
C | C++ | Java
• Insertion at beginning in singly Linked List  –
C | C++Java
• Insertion at nth position in singly Linked List  –
C | C++Java
• Insertion at end in singly Linked List  –
C | C++Java
• Deletion in singly Linked List  –
C | C++Java
• Deletion from beginning in singly linked list :
C | C++ | Java
• Deletion from nth position in singly linked list :
C | C++ | Java
• Deletion from end in singly linked list :
C | C++ | Java
• Linked List Insertion and Deletion –
C | C++Java
• Reverse a linked list without changing links between nodes (Data reverse only) –
C | C++Java
• Reverse a linked list by changing links between nodes –
C | C++Java
• Print reverse of a linked list without actually reversing –
C |C++Java
• Print reverse of a linked list without actually reversing –
C |C++Java
• Insertion in the middle Singly Linked List –
C | C++Java
• Insertion in a Sorted Linked List –
C | C++Java
• Delete alternate nodes of a Linked List –
C | C++Java
• Find middle of the linked list –
C | C++Java
• Reverse a linked list in groups of given size –
C | C++Java
• Find kth node from end of the linked list –
C | C++Java
• Append the last n nodes of a linked list to the beginning of the list –
C | C++Java
• Check whether linked list is palindrome or not –
C | C++Java
• Fold a Linked List –
C | C++Java
• Insert at given Position –
C | C++Java
• Deletion at given Position –
C | C++Java