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
#includeusing 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 "<
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(); } }
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
#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 "<
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.
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.