.png)
Deleting a Given Key from a Singly Linked List
Problem Statement
Given the head pointer of a singly linked list and a key value, delete the first node in the linked list whose data matches the given key.
Return the updated head of the linked list.
If the key is not found, the list should remain unchanged.
Understanding the Core Idea
In a singly linked list, each node contains:
- Data
- Pointer to the next node
When deleting a node, we must carefully update pointers to maintain the structure of the list.
There are three possible cases:
The node to delete is the head node.
The node to delete is in the middle.
The node to delete is the last node.
Since this is a singly linked list, we cannot move backward. Therefore, while traversing, we must keep track of the previous node.
Algorithm
If head is NULL → return NULL.
If head->data equals key:
- Store head in a temporary variable.
- Move head to head->next.
- Free/Delete the old head.
- Return new head.
Otherwise:
- Initialize two pointers:
- prev = NULL
- curr = head
- Traverse until curr is NULL or curr->data equals key.
- If key not found → return head.
- Otherwise:
- prev->next = curr->next
- Free/Delete curr.
- Return head.
Time and Space Complexity
Time Complexity: O(n)
Space Complexity: O(1)
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
struct Node* deleteKey(struct Node* head, int key) {
if (head == NULL)
return NULL;
// Case 1: head node needs to be deleted
if (head->data == key) {
struct Node* temp = head;
head = head->next;
free(temp);
return head;
}
struct Node* curr = head;
struct Node* prev = NULL;
// Traverse the list
while (curr != NULL && curr->data != key) {
prev = curr;
curr = curr->next;
}
// Key not found
if (curr == NULL)
return head;
// Delete node
prev->next = curr->next;
free(curr);
return head;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
}
int main() {
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 10;
head->next = (struct Node*)malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = (struct Node*)malloc(sizeof(struct Node));
head->next->next->data = 30;
head->next->next->next = NULL;
head = deleteKey(head, 20);
printf("Linked List after deleting key 20: ");
printList(head);
return 0;
}Output:
Linked List after deleting key 20: 10 30
C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int val) {
data = val;
next = NULL;
}
};
Node* deleteKey(Node* head, int key) {
if (head == NULL)
return NULL;
// Case 1: Delete head
if (head->data == key) {
Node* temp = head;
head = head->next;
delete temp;
return head;
}
Node* curr = head;
Node* prev = NULL;
// Traverse
while (curr != NULL && curr->data != key) {
prev = curr;
curr = curr->next;
}
// Key not found
if (curr == NULL)
return head;
// Delete node
prev->next = curr->next;
delete curr;
return head;
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
int main() {
Node* head = new Node(10);
head->next = new Node(20);
head->next->next = new Node(30);
head = deleteKey(head, 20);
cout << "Linked List after deleting key 20: ";
printList(head);
return 0;
}
Output:
Linked List after deleting key 20: 10 30
Java Implementation
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class Main {
public static Node deleteKey(Node head, int key) {
if (head == null)
return null;
if (head.data == key) {
return head.next;
}
Node curr = head;
Node prev = null;
while (curr != null && curr.data != key) {
prev = curr;
curr = curr.next;
}
if (curr == null)
return head;
prev.next = curr.next;
return head;
}
public static void printList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head = deleteKey(head, 20);
System.out.print("Linked List after deleting key 20: ");
printList(head);
}
}
Output:
Linked List after deleting key 20: 10 30
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def delete_key(head, key):
if head is None:
return None
if head.data == key:
return head.next
curr = head
prev = None
while curr and curr.data != key:
prev = curr
curr = curr.next
if curr is None:
return head
prev.next = curr.next
return head
def print_list(head):
while head:
print(head.data, end=" ")
head = head.next
print()
head = Node(10)
head.next = Node(20)
head.next.next = Node(30)
head = delete_key(head, 20)
print("Linked List after deleting key 20:", end=" ")
print_list(head)
Output:
Linked List after deleting key 20: 10 30
Next problem in the series:
Deleting a Node at a Given Position in a Singly Linked List
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
