Deleting A Node In A Linked List In C

Last Updated on March 11, 2022 by Ria Pathak

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

Delete a node with a given key from the given linked list and in case there are multiple occurrences of a given key in the linked list, then delete the first occurrence of this key in the linked list.

Problem Statement Understanding

According to the problem statement, we are given a linked list and we have to delete a node with a given key value, it may be present anywhere in the linked list but, there can be two different situations are first being when there is more than one node having the same key and the next being when the node is not at all present in the linked list, so now, you all might think that what we need to do?

In the case where there are multiple nodes, you will just have to delete the first node in the linked list with the value equal to the key, and in the case where the node to be deleted is not present at all in the linked list then simply return and exit the program.

Now, let us understand this problem by taking a very simple example:

If the given linked list is:

key = 7

• According to the problem statement, we have been provided a linked list and a key, and we need to delete the key from the given linked list.
• As we can see in the above example, 7 is present in the linked list which needs to be deleted.
• So after deleting the key from the linked list, the resultant linked list will be:

Let’s see another example:

If the given linked list is: 1 → 2 → 3 → 4 → 5 and key = 4

• According to the problem statement, we have been provided a linked list and a key, and we need to delete the key from the given linked list.
• As we can see in the above example, 4 is present in the linked list which needs to be deleted.
• So after deleting the key from the linked list, the resultant linked list will be 1 → 2 → 3 → 5.

Now I think from the above examples, the problem is clear. So let’s see how we can approach it.

Before moving to the approach section, try to think about how you can approach this problem.

• If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section. Now, first, let’s discuss the recursive approach to this problem and understand how it works, we will simply follow the steps to understand initially how recursion works for deleting a node from the linked list.

Approach: (Recursive)

• Now, if we think carefully, the current node is accessed by the previous node’s next, which is passed by reference. Thus, we can say that if we update the current node, previous node’s next will also get updated.
• So, we will traverse the linked list with the help of recursion, and when the data of head is equal to the value to be deleted, we will store the head in del_node, do head = head → next and then delete del_node and then return and terminate the function as our task is completed.
• By doing the above steps, the node will get deleted and as discussed above, when we will do head = head → next, it will make the previous → next point to head → next.

I hope the above approach might have just given you the basic idea of how recursion will work here, so now let’s look at the algorithm for this method

Algorithm: (Recursive)

Now, let’s completely understand the algorithm behind the recursive method, and we will simply follow the steps to delete the node with the given key.

• Create a function deleteNodeWithKey to delete the node with the given key and pass head by reference to the function and the key.
• Check if head is NULL, that means the list is empty or the node to be deleted is not in the list. Simply, return.
  • Else, check if *((head)->val == key), that means current node is the node to be deleted. Now, create a temporary variable del_node to store the node to be deleted. Now free del_node* variable and update head = (*head)->next; so that previous node’s next become head->next and return.
    As we know that the current node is accessed by the previous node’s next, which is passed by reference. hus, we can say that if we update the current node, previous node’s next will also get updated.
    • Else, Recursively call the function deleteNodeWithKey and pass the reference to the next node in the linked list *deleteNodeWithKey(&((head)->next), key);**.

Dry run

Code

#include 
#include 

// A linked list node
struct Node {
	int val;
	struct Node* next;
};
// Function to insert the node
void pushNode(struct Node** head_ref, int data)
{
	struct Node* new_node
		= (struct Node*)malloc(sizeof(struct Node));
	new_node->val = data;
	new_node->next = (*head_ref);
	(*head_ref) = new_node;
}

// Function to delete the node with the given key
void deleteNodeWithKey(struct Node** head, int key)
{
	// If head is NULL, then the list is empty
	if (head == NULL) {
		return;
	}

	// If current node is the node to be deleted 
	if ((*head)->val == key) {
		struct Node* del_node = (*head);
        *head = (*head)->next;
        free(del_node);
        return;
	}
	
	deleteNodeWithKey(&((*head)->next), key); // Recursively call the function passing the reference and key to the node
}

// Print the linked list
void printList(struct Node* node)
{
	while (node != NULL) {
		printf(" %d ", node->val);
		node = node->next;
	}
}

//Print the linked list after deletion
void printListPostDeletion(struct Node* node)
{
	while (node != NULL) {
               	if(node->val != 0)
			printf(" %d ", node->val);
		node = node->next;
	}
}

// Driver code
int main()
{
	/* Start with the empty list */
	struct Node* head = NULL;

	pushNode(&head, 1);
	pushNode(&head, 5);
	pushNode(&head, 7);
	pushNode(&head, 15);
    pushNode(&head, 20);
    printf("Linked list before deleting the key\n");
	printList(head);
	printf("\n");
	deleteNodeWithKey(&head, 7);
    printf("Linked list after deleting the key\n");
	printListPostDeletion(head);
	return 0;
}

Output
Linked list before deleting the key
20 → 15 → 7 → 5 → 1
Linked list after deleting the key
20 → 15 → 5 → 1

Time Complexity: The time complexity of this algorithm will be O(n), where n is the number of nodes in the given linked list

Space Complexity: The space complexity of the above algorithm will be O(n) due to recursion.

Now, let’s see iterative approach.

Approach (Iterative Method)

Now, let us discuss the most common and easiest approach to delete a node from the linked list.

• Iterate to the node which is present just before the node to be deleted.
• Now, set the next of the current node to the next of the node to be deleted.
• Then, free the memory of the node to be deleted.

Now, you all might be a bit clear from the approach on what we need to do exactly right?

Now, to get a bit more clear understanding of the implementation let us have a look at the algorithm which explains the full operation step by step

Algorithm (Iterative Method)

Now, let’s understand the algorithm on how to implement and think upon the code which we have to write for solving the given problem:

• Declare a pointer node_itr which will initially point to head and will be used to iterate through the linked list which will help us to find the node to be deleted and another pointer prev_node which will initially point to NULL and point to the previous node of the node which has to be deleted.
• Now, check if node_itr is not NULL and node_itr->data==key that means the key to be deleted is the head node, then we will change the reference to the head node to the next node of node_itr and delete node_itr and return.
• Else, move node_itr forward and also keep track of previous node node_prev = node_itr and search for the node with the given key to be deleted in the linked list.
• Now, if node_itr becomes NULL that means the node is not present in the given linked list then simply return and end the process.
• Else, point the next of the prev_node to next of node_itr, the node which has to be deleted, and finally delete the node.

Dry Run:

Code Implementation

#include 
#include 

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

void pushNode(struct Node** head_ref, int data)
{
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

// Function to delete the node with given key
void deleteGivenNode(struct Node** head_ref, int key)
{
    struct Node *node_itr = *head_ref, *prev_node;

    if (node_itr != NULL && node_itr->data == key) {
        *head_ref = node_itr->next;
        free(node_itr);
        return;
    }

    while (node_itr != NULL && node_itr->data != key) {
        prev_node= node_itr;
        node_itr= node_itr->next;
    }

    if (node_itr == NULL)
        return;

    prev_node->next = node_itr->next;

    free(node_itr);
}

//Function to print the linked list
void printList(struct Node* node)
{
    while (node != NULL) {
        printf(" %d ", node->data);
        node = node->next;
    }
}

int main()
{
    struct Node* head = NULL;

    pushNode(&head, 1);
    pushNode(&head, 5);
    pushNode(&head, 7);
    pushNode(&head, 15);
    pushNode(&head, 20);
    
    printf("Linked list before deleting the key\n");
    printList(head);
    printf("\n");
    printf("Linked list after deleting the key\n");
    deleteGivenNode(&head, 1);
    printList(head);
    return 0;
}

Output
Linked list before deleting the key
20 → 15 → 7 → 5 → 1
Linked list after deleting the key
20 → 15 → 7 → 5

Time Complexity: The time complexity of this algorithm will be O(n), where n is the number of nodes in the given linked list

Space Complexity: The space complexity of the above algorithm will be O(1) as we are not using any additional data structure to manipulate the nodes

So, in this article, we have tried to explain the most efficient approach to flatten a binary tree to a linked list. This is an important question when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.