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

Categories Data Structures 11 mins read

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.

Delete all nodes by key in a linked list

Required knowledge

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

Let us suppose the node structure as

struct node
{
    int data;          // Data
    struct node *next; // Address
} * head;

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
    struct node *next; // Address
} * head;


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

    head = malloc(sizeof(struct node));

    /*
     * Unable to allocate memory, hence exit from app.
     */
    if (head == NULL)
    {
        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);

    head->data = data; // Link data field with data
    head->next = NULL; // Link address field to NULL

    temp = head;

    /*
     * 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.
     */
    if (head == NULL)
    {
        printf("List is empty.\n");
        return;
    }
    
    temp = head;
    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 */
    while (head != NULL && head->data == key)
    {
        // Get reference of head node
        prev = head;

        // Adjust head node link
        head = head->next;

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

        // No need to delete further
        return;
    }

    prev = NULL;
    cur  = head;

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

            // Delete current node
            free(cur);

            // No need to delete further
            return;
        } 

        prev = cur;
        cur = cur->next;
    }
}
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
    struct node *next; // Address
} * head;


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

    head = malloc(sizeof(struct node));

    /*
     * Unable to allocate memory, hence exit from app.
     */
    if (head == NULL)
    {
        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);

    head->data = data; // Link data field with data
    head->next = NULL; // Link address field to NULL

    temp = head;

    /*
     * 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.
     */
    if (head == NULL)
    {
        printf("List is empty.\n");
        return;
    }
    
    temp = head;
    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 */
    if (head != NULL && head->data == key)
    {
        // Copy head node reference to last node to del
        lastNodeToDel = head;
    }

    cur = head;

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

            // Adjust links for previous node
            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;
        }
        
        // Adjust head link if head needs to be deleted
        if (lastNodeToDel == head)
        {
            head = head->next;
        }

        // Delete node
        free(lastNodeToDel);
    }
}
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

Convert to regular block then edit/**
 * 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
    struct node *next; // Address
} * head;


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

    head = malloc(sizeof(struct node));

    /*
     * Unable to allocate memory, hence exit from app.
     */
    if (head == NULL)
    {
        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);

    head->data = data; // Link data field with data
    head->next = NULL; // Link address field to NULL

    temp = head;

    /*
     * 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.
     */
    if (head == NULL)
    {
        printf("List is empty.\n");
        return;
    }
    
    temp = head;
    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 */
    while (head != NULL && head->data == key)
    {
        // Get reference of head node
        prev = head;

        // Adjust head node link
        head = head->next;

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

        totalDeleted++;
    }

    prev = NULL;
    cur  = head;

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

            // Delete current node
            free(cur);

            cur = prev->next;

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

    }

    return totalDeleted;
}
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,