# C program to delete all nodes by key in a linked list

Write a C program to create a linked list and delete all nodes by key. How to delete element by key of a linked list in C program. In previous few programs, I explained how to delete first, last or nth element from a singly linked list. In this post I will explain how to delete all nodes by key in a linked list, delete first node by key or delete last node by key in C program.

## Required knowledge

Singly linked list, Functions, Pointers, Structures, Dynamic memory allocation

Let us suppose the node structure as

``````struct node
{
int data;          // Data

Where `head` is a pointer to first node.

Note: To keep this post short, readable and quick to consume. I have not explained logic to create and traverse list.

## How to delete first element by key?

Step by step descriptive logic to delete first element by key from a singly linked list.

1. Declare two variables that are pointer to our node. Say `struct node *prev, *cur`.
2. Check if data of `head` node contains `key` to delete. If it does then, copy reference of `head` node to some temp node say `prev`. Adjust link for `head` node, to its next node and delete it.
3. If `head` does not contain element to delete, then assign `cur = head;` and `prev = NULL;`.
4. Check if data of current node is equal to `key` to delete. If it does, you got node to delete. Wait before deleting we need to adjust previous node links.

If `prev` node is not `NULL` then make sure `prev` node points to element next to `cur` node i.e. `prev->next = cur->next;`.
Finally delete `cur` node using `free(cur)` and terminate from function.

5. Assign current node to previous node i.e. `prev = cur`. Move current node to next i.e. `cur = cur->next;`.
6. Repeat step 5-6 till last node in the list.

### Program to delete first element by key

``````/**
* C program to delete first node from Singly Linked List by key.
*/
#include <stdio.h>
#include <stdlib.h>

/* Node structure */
struct node
{
int data;          // Data

/* Function declaration */
void createList(int n);
void deleteFirstByKey(int key);
void displayList();

int main()
{
int n, key;

// Input node count to create
printf("Enter number of node to create: ");
scanf("%d", &n);

createList(n);

// Display list
printf("\nData in list before deletion\n");
displayList();

printf("\nEnter element to delete with key: ");
scanf("%d", &key);

// Call function to delete first element by key
deleteFirstByKey(key);

// Print final list
printf("\nData in list after deletion\n");
displayList();

return 0;
}

/**
* Create a list of n nodes
*/
void createList(int n)
{
struct node *newNode, *temp;
int data, i;

/*
* Unable to allocate memory, hence exit from app.
*/
{
printf("Unable to allocate memory. Exiting from app.");
exit(0);
}

/* Input head node data from user */
printf("Enter data of node 1: ");
scanf("%d", &data);

/*
* Create n nodes and add to the list
*/
for (i = 2; i <= n; i++)
{
newNode = malloc(sizeof(struct node));

/* If memory is not allocated for newNode */
if (newNode == NULL)
{
printf("Unable to allocate memory. Exiting from app.");
exit(0);
}

printf("Enter data of node %d: ", i);
scanf("%d", &data);

newNode->data = data; // Link data field of newNode
newNode->next = NULL; // The newNode should point to nothing

temp->next = newNode; // Link previous node i.e. temp to the newNode
temp = temp->next;
}

}

/**
* Display entire list
*/
void displayList()
{
struct node *temp;

/*
* If the list is empty i.e. head = NULL,
* dont perform any action and return.
*/
{
printf("List is empty.\n");
return;
}

while (temp != NULL)
{
printf("%d, ", temp->data);

temp = temp->next;  // Move to next node
}

printf("\n");
}

/**
* Delete first node by key from the list.
*/
void deleteFirstByKey(int key)
{
struct node *prev, *cur;

/* Check if head node contains key */
{
// Get reference of head node

// Delete prev since it contains reference to head node
free(prev);

// No need to delete further
return;
}

prev = NULL;

/* For each node in the list */
while (cur != NULL)
{
// Current node contains key
if (cur->data == key)
{
if (prev != NULL)
prev->next = cur->next;

// Delete current node
free(cur);

// No need to delete further
return;
}

prev = cur;
cur = cur->next;
}
}``````
Output

```Enter number of node to create: 5
Enter data of node 1: 1
Enter data of node 2: 2
Enter data of node 3: 3
Enter data of node 4: 4
Enter data of node 5: 5

Data in list before deletion
1, 2, 3, 4, 5,

Enter element to delete with key: 1

Data in list after deletion
2, 3, 4, 5,```

## How to delete last element by key?

Deleting last node by key is little tricky then deleting first. We will use same logic, in addition we need to keep track of last node that contains key and node previous to it.

Step by step descriptive logic to delete last node by key from a list.

1. Declare four variables that are pointer to our node. Say `struct node *prevToLast, *lastNodeToDel, *prev, *cur;`. Initialize all of them with `NULL`.
2. Check if data of `head` node contains `key` to delete. If it does then, copy reference of `head` node to `lastNodeToDel`.
3. Initialize `cur` with `head`.
4. Check if `(cur->data == key)`. If it does, you got node to delete, but we won't delete it immediately since it may not be the last node containing key. Hence, assign `cur` to `lastNodeToDel`. Assign `prev` to `prevToLast`, if `prev != NULL`.
5. Copy `cur` to `prev` node. Move current node to next node i.e. `cur = cur->next;`.
6. Repeat step 4-5 till last node.
7. If `lastNodeToDel != NULL`, then we have a node to delete. But, before deleting we need to adjust its previous node link. Link `prevToLast->next = lastNodeToDel->next`. If `lastNodeToDel` is `head` node. Then, adjust link of `head` node to point to its next node i.e. `head = head->next;`.
8. Finally delete `lastNodeToDel` and you are done.

### Program to delete last element by key

``````/**
* C program to delete last node from Singly Linked List by key.
*/
#include <stdio.h>
#include <stdlib.h>

/* Node structure */
struct node
{
int data;          // Data

/* Function declaration */
void createList(int n);
void deleteLastByKey(int key);
void displayList();

int main()
{
int n, key;

// Input node count to create
printf("Enter number of node to create: ");
scanf("%d", &n);

createList(n);

// Display list
printf("\nData in list before deletion\n");
displayList();

printf("\nEnter element to delete with key: ");
scanf("%d", &key);

// Call function to delete last element by key
deleteLastByKey(key);

// Print final list
printf("\nData in list after deletion\n");
displayList();

return 0;
}

/**
* Create a list of n nodes
*/
void createList(int n)
{
struct node *newNode, *temp;
int data, i;

/*
* Unable to allocate memory, hence exit from app.
*/
{
printf("Unable to allocate memory. Exiting from app.");
exit(0);
}

/* Input head node data from user */
printf("Enter data of node 1: ");
scanf("%d", &data);

/*
* Create n nodes and add to the list
*/
for (i = 2; i <= n; i++)
{
newNode = malloc(sizeof(struct node));

/* If memory is not allocated for newNode */
if (newNode == NULL)
{
printf("Unable to allocate memory. Exiting from app.");
exit(0);
}

printf("Enter data of node %d: ", i);
scanf("%d", &data);

newNode->data = data; // Link data field of newNode
newNode->next = NULL; // The newNode should point to nothing

temp->next = newNode; // Link previous node i.e. temp to the newNode
temp = temp->next;
}

}

/**
* Display entire list
*/
void displayList()
{
struct node *temp;

/*
* If the list is empty i.e. head = NULL,
* dont perform any action and return.
*/
{
printf("List is empty.\n");
return;
}

while (temp != NULL)
{
printf("%d, ", temp->data);
temp = temp->next;    // Move to next node
}
printf("\n");
}

/**
* Delete last node having data as given key.
*/
void deleteLastByKey(int key)
{
struct node *prevToLast, *lastNodeToDel, *prev, *cur;

prev = NULL;
prevToLast    = NULL;
lastNodeToDel = NULL;

/* Check if head node contains key */
{
// Copy head node reference to last node to del
}

/* For each node in the list */
while (cur != NULL)
{
// Current node contains key
if (cur->data == key)
{
lastNodeToDel = cur;

if (prev != NULL)
{
prevToLast = prev;
}
}
prev = cur;
cur = cur->next;
}

// Delete last element if key found
if (lastNodeToDel != NULL)
{
// Link prev last with node next to last node to delete
if (prevToLast != NULL)
{
prevToLast->next = lastNodeToDel->next;
}

{
}

// Delete node
free(lastNodeToDel);
}
}``````
Output

```Enter number of node to create: 5
Enter data of node 1: 1
Enter data of node 2: 2
Enter data of node 3: 3
Enter data of node 4: 4
Enter data of node 5: 1

Data in list before deletion
1, 2, 3, 4, 1,

Enter element to delete with key: 1

Data in list after deletion
1, 2, 3, 4,```

## How to delete all nodes by key?

Logic to delete all nodes by key from a linked list is similar to deletion of first node. However, in first program to delete first element by key we terminated from function after deleting first node. But, here we will not terminate after deleting first element containing key.

### Program to delete all nodes by key

``````/**
* C program to delete all nodes by given key in Singly Linked List.
*/
#include <stdio.h>
#include <stdlib.h>

/* Node structure */
struct node
{
int data;          // Data

/* Function declaration */
void createList(int n);
int  deleteAllByKey(int key);
void displayList();

int main()
{
int n, key, totalDeleted;

// Input node count to create
printf("Enter number of node to create: ");
scanf("%d", &n);

createList(n);

// Display list
printf("\nData in list before deletion\n");
displayList();

printf("\nEnter element to delete with key: ");
scanf("%d", &key);

totalDeleted = deleteAllByKey(key);
printf("%d elements deleted with key %d.\n", totalDeleted, key);

// Print final list
printf("\nData in list after deletion\n");
displayList();

return 0;
}

/**
* Create a list of n nodes
*/
void createList(int n)
{
struct node *newNode, *temp;
int data, i;

/*
* Unable to allocate memory, hence exit from app.
*/
{
printf("Unable to allocate memory. Exiting from app.");
exit(0);
}

/* Input head node data from user */
printf("Enter data of node 1: ");
scanf("%d", &data);

/*
* Create n nodes and add to the list
*/
for (i = 2; i <= n; i++)
{
newNode = malloc(sizeof(struct node));

/* If memory is not allocated for newNode */
if (newNode == NULL)
{
printf("Unable to allocate memory. Exiting from app.");
exit(0);
}

printf("Enter data of node %d: ", i);
scanf("%d", &data);

newNode->data = data; // Link data field of newNode
newNode->next = NULL; // The newNode should point to nothing

temp->next = newNode; // Link previous node i.e. temp to the newNode
temp = temp->next;
}

}

/**
* Display entire list
*/
void displayList()
{
struct node *temp;

/*
* If the list is empty i.e. head = NULL,
* dont perform any action and return.
*/
{
printf("List is empty.\n");
return;
}

while (temp != NULL)
{
printf("%d, ", temp->data);     // Print data of current node
temp = temp->next;              // Move to next node
}
printf("\n");
}

/**
* Delete all nodes having data as given key.
*/
int deleteAllByKey(int key)
{
int totalDeleted = 0;
struct node *prev, *cur;

/* Check if head node contains key */
{
// Get reference of head node

// Delete prev since it contains reference to head node
free(prev);

totalDeleted++;
}

prev = NULL;

/* For each node in the list */
while (cur != NULL)
{
// Current node contains key
if (cur->data == key)
{
if (prev != NULL)
{
prev->next = cur->next;
}

// Delete current node
free(cur);

cur = prev->next;

totalDeleted++;
}
else
{
prev = cur;
cur = cur->next;
}

}

}``````
Output

```Enter number of node to create: 5
Enter data of node 1: 1
Enter data of node 2: 2
Enter data of node 3: 1
Enter data of node 4: 1
Enter data of node 5: 5

Data in list before deletion
1, 2, 1, 1, 5,

Enter element to delete with key: 1
3 elements deleted with key 1.

Data in list after deletion
2, 5,```

Happy coding ðŸ˜‰