Last Updated on March 10, 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
In this question, we are given a singly linked list and a value X. We have to delete the first occurrence of a node with the data X from the linked list.
Note: Although there can be multiples nodes with value X in the linked list, but we have to only delete the first node with value X from the linked list.
Problem Statement Understanding
Let’s try to understand the problem statement with the help of examples.
Suppose the given linked list is: 1 → 1 → 0 → 2 → 2 and the value to be deleted is 0.
- Now, according to the problem statement, we have to delete the first occurrence of the node containing the value 0.
- So, the linked list after deleting 0 will be 1 → 1 → 2 → 2.
Suppose the list is:.
and the value to be deleted is 2
- Now, in this case, we can see that there are two nodes with data 2 in the linked list. According to the problem statement, we only need to delete the first occurrence of the node with value 2 from the linked list.
- Our output linked list after deletion will be
Some more examples
Sample Input 1: 1 → 2 → 3 →4, Value to be deleted (X) = 2
Sample Output 1: 1 → 3 → 4
Sample Input 2: 1 → 1 → 2 →2, Value to be deleted (X) = 1
Sample Output 2: 1 → 2 → 2
Now, I think from the above examples, the problem statement is clear. Let’s see how we can approach it.
Before moving to the approach section, try to think about how can you 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.
Approach (Iterative)
Let us first think about what we should do to delete a node from a linked list.
Let us take an example. 1 → 2 → 3 → 4. Now, to delete 2 from the list, what should we do?
- What if we make 1 point to 3 instead of 2 ? Yes. That’s the essence.
To delete a node P from a linked list, we have to traverse to its previous node and make it point to the P‘s next node.
Let’s see the algorithm.
Algorithm
- Create a pointer temp and make it point to the head of the list and also create a pointer prev and point it to NULL.
- If the head contains the value X, make head = temp → next, and then delete temp.
- Else, we will traverse the list with temp and store temp in pointer prev before incrementing it.
- The loop will run till temp → data! = X.
- As soon as temp → data = X, the loop will break.
- As we were storing temp in prev before incrementing it, so prev now points to the previous node of the node which we want to delete.
- Now, we will simply do prev -> next = temp -> next, as discussed in the approach.
- Finally, delete temp.
- In this way, the first occurrence of a node with value X will be deleted. If the list is traversed and the value is not found, we will simply return.
Dry Run
Code Implementation
#include <stdio.h> #include <stdlib.h> // A linked list node struct Node { int data; struct Node* next; }; /* Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list. */ void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Given a reference (pointer to pointer) to the head of a list and a key, deletes the first occurrence of key in linked list */ void deleteNode(struct Node** head_ref, int key) { // Store head node struct Node *temp = *head_ref, *prev; // If head node itself holds the key to be deleted if (temp != NULL && temp->data == key) { *head_ref = temp->next; // Changed head free(temp); // free old head return; } // Search for the key to be deleted, keep track of the // previous node as we need to change 'prev->next' while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } // If key was not present in linked list if (temp == NULL) return; // Unlink the node from linked list prev->next = temp->next; free(temp); // Free memory } // This function prints contents of linked list starting // from the given node void printList(struct Node* node) { while (node != NULL) { printf(" %d ", node->data); node = node->next; } } // Driver code int main() { /* Start with the empty list */ struct Node* head = NULL; push(&head, 7); push(&head, 1); push(&head, 3); push(&head, 2); puts("Created Linked List: "); printList(head); deleteNode(&head, 1); puts("\nLinked List after Deletion of 1: "); printList(head); return 0; }
#include <bits/stdc++.h> using namespace std; /* Node structure of linked list node */ class Node{ public: int data; Node* next; }; /* Using this function we will insert a new node at head of linked list */ void push(Node** head_ref, int new_data) { Node* new_node = new Node(); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Using this function we will be deleting the first occurance of a node with value = key from the linked list */ void deleteValue(Node** head_ref, int key) { Node* temp = *head_ref; Node* prev = NULL; if (temp != NULL && temp->data == key) { *head_ref = temp->next; delete temp; return; } else { while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } if (temp == NULL) return; prev->next = temp->next; delete temp; } } /* Using this function we will be printing the content of linked list */ void print(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } int main() { Node* head = NULL; push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); puts("Created Linked List: "); print(head); int X = 2; deleteValue(&head, X); cout<<"\nLinked List after Deletion of first occurance of node with value "<<X<<": "<<endl; print(head); return 0; }
public class LinkedList { Node head; /* Node structure of a linked list node */ class Node { int data; Node next; Node(int d) { data = d; next = null; } } /* Using this function we will be deleting the first occurance of a node with value = key from the linked list */ void deleteValue(int key) { Node temp = head, prev = null; if (temp != null && temp.data == key) { head = temp.next; return; } while (temp != null && temp.data != key) { prev = temp; temp = temp.next; } if (temp == null) return; prev.next = temp.next; } /* Using this function we will insert a new node at head of linked list */ public void push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } /* Using this function we will be printing the content of linked list */ public void printList() { Node tnode = head; while (tnode != null) { System.out.print(tnode.data + " "); tnode = tnode.next; } } public static void main(String[] args) { LinkedList llist = new LinkedList(); llist.push(4); llist.push(3); llist.push(2); llist.push(1); System.out.println("\nCreated Linked list is:"); llist.printList(); int X = 2; llist.deleteValue(X); System.out.println( "\nLinked List after Deletion of first occurance of node with value "+X+": "); llist.printList(); } }
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node def deleteNode(self, key): temp = self.head if (temp is not None): if (temp.data == key): self.head = temp.next temp = None return while(temp is not None): if temp.data == key: break prev = temp temp = temp.next if(temp == None): return prev.next = temp.next temp = None def printList(self): temp = self.head while(temp): print (temp.data, end = " ") temp = temp.next llist = LinkedList() llist.push(4) llist.push(3) llist.push(2) llist.push(1) print ("Created Linked List: ") llist.printList() llist.deleteNode(2) print ("\nLinked List after Deletion of 2:") llist.printList()
Output
Created Linked List:
1 2 3 4
Linked List after Deletion of first occurance of node with value 2:
1 3 4
Time Complexity: O(n), as list traversal is needed.
Space Complexity: O(1), as only temporary variables are being created.
Approach (Recursive)
As we have already discussed what we have to do to delete a node from a linked list, now here we will modify it a lit bit while implementing.
- 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 altering the current node can alter the previous node’s next.
- So, we will traverse the linked list with the help of recursion, and when the head’s data is equal to the value of node to be deleted(X), we will store the head in temp, do head = head → next and delete temp and then return 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.
Let’s see the algorithm.
Algorithm
- Base case – If the head is NULL, i.e., the node with value X is not present in the list, so we will print Element not present in the list and then we will return.
- If the head → data = X, then store the head in a pointer temp, do head = head → next and delete temp and then return as our task is completed. This will change the required links too as discussed above.
- Keep recurring with deleteValue( head – > next, X).
Dry Run
Code Implementation
#include#include /* Link list node */ struct Node { int data; struct Node* next; }; /* Recursive Function to delete the entire linked list */ void deleteList(struct Node* head) { if (head == NULL) return; deleteList(head->next); free(head); } /* Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. */ void push(struct Node** head_ref, int new_data) { struct Node* new_node = new Node; new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Driver program to test count function*/ int main() { /* Start with the empty list */ struct Node* head = NULL; /* Use push() to construct below list 1->12->1->4->1 */ push(&head, 1); push(&head, 4); push(&head, 1); push(&head, 12); push(&head, 1); printf("\n Deleting linked list"); deleteList(head); // Since head now points to illgal address, we should set head = NULL: head = NULL; printf("\nLinked list deleted"); return 0; }
#includeusing namespace std; struct node { int info; node* link = NULL; node() {} node(int a) : info(a) { } }; /* Using this function we will be deleting the first occurance of the given valued node from the linked list */ void deleteValue(node*& head, int value) { if (head == NULL) { cout << "Element not present in the list\n"; return; } if (head->info == value) { node* temp = head; head = head->link; delete (temp); return; } deleteValue(head->link, value); } /* Using this function we will push the node in the list */ void push(node*& head, int data) { node* newNode = new node(data); newNode->link = head; head = newNode; } /* Using this function we will print the content of linked list */ void print(node* head) { if (head == NULL and cout << endl) return; cout << head->info << ' '; print(head->link); } int main() { node* head = NULL; push(head, 4); push(head, 3); push(head, 2); push(head, 1); puts("Created Linked List: "); print(head); int X = 2; deleteValue(head, X); cout<<"\nLinked List after Deletion of first occurance of node with value "<
class Node { int info; Node link =null; Node(int info) { this.info=info; } } class DeletingNode { void push(Node head,int data) { Node newNode = new Node(data); newNode.link = head; head=newNode; } void print(Node head) { Node temp=head; while(temp!=null){ System.out.print(temp.info+" "); temp=temp.link; } } void deleteValue(Node head,int value) { if(head==null || head.link==null) { System.out.println("Element not present in the list"); return; } if(head.link.info==value) { Node x =head; x.link=head.link.link; return; } deleteValue(head.link, value); } public static void main(String[] args) { Node head=null; DeletingNode ll=new DeletingNode(); ll.push(head, 4); ll.push(head, 3); ll.push(head, 2); ll.push(head, 1); System.out.println("Created linked list :"); ll.print(head); int x=2; ll.deleteValue(head, x); Node temp=head; System.out.println("Linked list after deletion of first occurance of node with value "+x); ll.print(temp); } }
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node def printList(self): temp = self.head while(temp): print (temp.data, end = " ") temp = temp.next def deleteNode(head, key): if head == None: print("Element not present in the list") return if head.data == key: temp = head head = head.next del temp return deleteNode(head.next, key) llist = LinkedList() llist.push(4) llist.push(3) llist.push(2) llist.push(1) print ("Created Linked List: ") llist.printList() deleteNode(llist.head, 2) print ("\nLinked List after Deletion of 2:") llist.printList()
Output
Created Linked List:
1 2 3 4
Linked List after Deletion of first occurance of node with value 2:
1 3 4
Time Complexity: O(n), as list traversal is needed.
[forminator_quiz id=”5290″]
So, in this article, we have tried our best to explain how to delete a node from 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.