.png)
Deleting a Node at a Given Position in a Singly Linked List
Problem Statement
Given the head pointer of a singly linked list and a position (1-based index), delete the node present at that position.
Return the updated head of the linked list.
If the position is invalid (greater than the length of the list or less than 1), the list should remain unchanged.
Understanding the Logic
In a singly linked list, deletion requires careful pointer manipulation.
There are two major scenarios:
- Deleting the first node (position = 1)
- Deleting any other node (middle or last)
Because this is a singly linked list, we cannot move backward. Therefore, we must:
- Traverse until position - 1
- Maintain a previous pointer
- Update the next reference properly
Algorithm
If head is NULL → return NULL.
If position == 1:
- Store head in temp
- Move head = head->next
- Free/Delete temp
- Return head
Otherwise:
- Traverse until position - 1
- If traversal ends before reaching position - 1 → invalid position
- Store node to delete in temp
- Update prev->next = temp->next
- Free/Delete temp
- 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* deleteAtPosition(struct Node* head, int position) {
if (head == NULL)
return NULL;
if (position == 1) {
struct Node* temp = head;
head = head->next;
free(temp);
return head;
}
struct Node* prev = head;
for (int i = 1; i < position - 1 && prev != NULL; i++) {
prev = prev->next;
}
if (prev == NULL || prev->next == NULL)
return head;
struct Node* temp = prev->next;
prev->next = temp->next;
free(temp);
return head;
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
}
int main() {
struct Node* head = malloc(sizeof(struct Node));
head->data = 10;
head->next = malloc(sizeof(struct Node));
head->next->data = 20;
head->next->next = malloc(sizeof(struct Node));
head->next->next->data = 30;
head->next->next->next = NULL;
head = deleteAtPosition(head, 2);
printf("Linked List after deleting position 2: ");
printList(head);
return 0;
}
Output:
Linked List after deleting position 2: 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* deleteAtPosition(Node* head, int position) {
if (head == NULL)
return NULL;
if (position == 1) {
Node* temp = head;
head = head->next;
delete temp;
return head;
}
Node* prev = head;
for (int i = 1; i < position - 1 && prev != NULL; i++) {
prev = prev->next;
}
if (prev == NULL || prev->next == NULL)
return head;
Node* temp = prev->next;
prev->next = temp->next;
delete temp;
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 = deleteAtPosition(head, 2);
cout << "Linked List after deleting position 2: ";
printList(head);
return 0;
}
Output:
Linked List after deleting position 2: 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 deleteAtPosition(Node head, int position) {
if (head == null)
return null;
if (position == 1)
return head.next;
Node temp = head;
for (int i = 1; i < position - 1 && temp != null; i++) {
temp = temp.next;
}
if (temp == null || temp.next == null)
return head;
temp.next = temp.next.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 = deleteAtPosition(head, 2);
System.out.print("Linked List after deleting position 2: ");
printList(head);
}
}
Output:
Linked List after deleting position 2: 10 30
Python Implementation
class Node:
def __init__(self, data):
self.data = data
self.next = None
def delete_at_position(head, position):
if head is None:
return None
if position == 1:
return head.next
temp = head
for _ in range(position - 2):
if temp is None:
return head
temp = temp.next
if temp is None or temp.next is None:
return head
temp.next = temp.next.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_at_position(head, 2)
print("Linked List after deleting position 2:", end=" ")
print_list(head)
Output:
Linked List after deleting position 2: 10 30
Next problem in the series:
Delete Entire Linked List in Data Structures
.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)
