Delete first occurrence of given Key from a Linked List
Given a linked list and a key to be deleted. The task is to delete the first occurrence of the given key from the linked list.
Note: The list may have duplicates.
Examples:
Input: list = 1->2->3->5->2->10, key = 2
Output: 1->3->5->2->10
Explanation: There are two instances of 2. But as per the question we need to delete the first occurrence only.Input: list = 3->3->3->3, key = 3
Output: 3->3->3
Approach:
The basic idea is to find the first occurrence of the key by traversing from the head and delete the node. The deletion of a node is explained in detail in Deletion in Linked List.
Follow the steps mentioned below to implement the idea:
- Start iterating from the given head of the linked list.
- If the data of the current node matches the given key, this is the first occurrence of the given key.
- So, delete this node and return the head of the modified linked list.
Below is the implementation of the above approach.
C
// A complete working C code to demonstrate // deletion of given key in singly linked list #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 a value, 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) { // Changed head *head_ref = temp->next; free(temp); 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); } // 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; }
C++
// A complete working C++ program to demonstrate // deletion of given key in singly linked #include <bits/stdc++.h> using namespace std; // A linked list node class Node { public: int data; Node* next; }; // Given a reference (pointer to pointer) to the head // of a list and a value, inserts a new node // on the front of the 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; } // 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(Node** head_ref, int key) { // Store head node Node* temp = *head_ref; Node* prev = NULL; // If head node itself holds // the key to be deleted if (temp != NULL && temp->data == key) { // Changed head *head_ref = temp->next; // Free old head delete temp; return; } // Else Search for the key to be // deleted, keep track of the // previous node as we need to // change 'prev->next' else { 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 memory delete temp; } } // This function prints contents of // linked list starting from the // given node void printList(Node* node) { while (node != NULL) { cout << node->data << " "; node = node->next; } } // Driver code int main() { // Start with the empty list Node* head = NULL; // Add elements in linked list 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; }
Java
// A complete working Java program to demonstrate // deletion of given key in singly linked list import java.io.*; public class LinkedList { Node head; // Linked list Node class Node { int data; Node next; Node(int d) { data = d; next = null; } } // Given a key, deletes the first // occurrence of key in // linked list void deleteNode(int key) { // Store head node Node temp = head, prev = null; // If head node itself holds the key to be deleted if (temp != null && temp.data == key) { // Changed head head = temp.next; return; } // Search for the key to be deleted, keep track of // the previous node as we need to change temp.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; } // Inserts a new Node at front of the list. public void push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } // This function prints contents of linked list // starting from the given node public void printList() { Node tnode = head; while (tnode != null) { System.out.print(tnode.data + " "); tnode = tnode.next; } } // Driver program to test above functions. Ideally this // function should be in a separate user class. It is kept // here to keep code compact public static void main(String[] args) { LinkedList llist = new LinkedList(); llist.push(7); llist.push(1); llist.push(3); llist.push(2); System.out.println("Created Linked List:"); llist.printList(); // Delete node with data 1 llist.deleteNode(1); System.out.println( "\nLinked List after Deletion of 1:"); llist.printList(); } }
Python3
# A complete working Python3 program to # demonstrate deletion in singly # linked list with class # Node class class Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None class LinkedList: # Function to initialize head def __init__(self): self.head = None # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Given a reference to the head of a list and a key, # delete the first occurrence of key in linked list def deleteNode(self, key): # Store head node temp = self.head # If head node itself holds the key to be deleted if (temp is not None): if (temp.data == key): self.head = temp.next temp = None return # Search for the key to be deleted, keep track of the # previous node as we need to change 'prev.next' while(temp is not None): if temp.data == key: break prev = temp temp = temp.next # If key was not present in linked list if(temp == None): return # Unlink the node from linked list prev.next = temp.next temp = None # Utility function to print the linked LinkedList def printList(self): temp = self.head while(temp): print(temp.data, end =" "), temp = temp.next # Driver code if __name__ == '__main__': llist = LinkedList() llist.push(7) llist.push(1) llist.push(3) llist.push(2) print("Created Linked List:") llist.printList() llist.deleteNode(1) print("\nLinked List after Deletion of 1:") llist.printList()
C#
// A complete working C# program // to demonstrate deletion in // singly linked list using System; class GFG { // Head of list Node head; // Linked list Node public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } // Given a key, deletes the first // occurrence of key in linked list void deleteNode(int key) { // Store head node Node temp = head, prev = null; // If head node itself holds // the key to be deleted if (temp != null && temp.data == key) { // Changed head head = temp.next; return; } // Search for the key to be // deleted, keep track of the // previous node as we need // to change temp.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; } // Inserts a new Node at // front of the list. public void Push(int new_data) { Node new_node = new Node(new_data); new_node.next = head; head = new_node; } // This function prints contents // of linked list starting from // the given node public void printList() { Node tnode = head; while (tnode != null) { Console.Write(tnode.data + " "); tnode = tnode.next; } } // Driver code public static void Main(String[] args) { GFG llist = new GFG(); llist.Push(7); llist.Push(1); llist.Push(3); llist.Push(2); Console.WriteLine("Created Linked List:"); llist.printList(); // Delete node with data 1 llist.deleteNode(1); Console.WriteLine( "\nLinked List after Deletion of 1:"); llist.printList(); } }
Javascript
// A complete working javascript program // to demonstrate deletion // in singly linked list // Head of list var head; // Linked list Node class Node { constructor(val) { this.data = val; this.next = null; } } // Given a key, deletes the first occurrence // of key in linked list function deleteNode(key) { // Store head node var temp = head, prev = null; // If head node itself holds the key to be deleted if (temp != null && temp.data == key) { // Changed head head = temp.next; return; } // Search for the key to be deleted, keep track of // the previous node as we need to change temp.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; } // Inserts a new Node at front of the list. function push(new_data) { var new_node = new Node(new_data); new_node.next = head; head = new_node; } // This function prints contents of linked list // starting from the given node function printList() { tnode = head; while (tnode != null) { console.log(tnode.data + " "); tnode = tnode.next; } } // Driver program to test above functions. // Ideally this function should be in a // separate user class. It is kept here to keep code compact push(7); push(1); push(3); push(2); console.log("Created Linked List: "); printList(); // Delete node with data 1 deleteNode(1); console.log("Linked List after Deletion of 1:"); printList();
Created Linked List: 2 3 1 7 Linked List after Deletion of 1: 2 3 7
Time Complexity: O(N) where N is the length of the linked list
Auxiliary Space: O(1)