Linked List Deletion
 Linked List Removal Algorithm
 Linked List Removal Illustration
 Linked List Removal Implementation
 Linked List Removal Algorithm Complexity
In this article, we will learn how to remove a node from a linked list.
Linked List Removal Algorithm
Let the head
be the pointer to the first node of the linked list, and let temp
be the value of the node to be removed from the linked list.
Iterative Algorithm

Initialize pointer
curr
to point towards thehead
to iterate over the linked list andprev
asNULL
to keep track of node beforetemp
when deleting it. 
If the node to be deleted is
head
i.e.temp
!=NULL
&&curr>data
==temp
, Sethead
ascurr>next
and deletecurr
. 
Else do the following until we reach the node to be deleted.
prev
=temp
.temp
=temp>next
.

if
temp
==NULL
, return; 
Set
prev>next
astemp>next
and delete thetemp
node.
Recursive Algorithm

If
head
==NULL
, the linked list is empty no element to delete. So, return; 
If
head>data
==temp
,i.e. we have found the node to be deleted Store
head
in a temporary nodet
.  Set
head
ashead>next
to remove the node.  Delete
t
and return to the earlier recursive call.
 Store

Recursively call
deleteNode()
onhead>next
if none of the above conditions match to keep looking for the node.
Linked List Removal Illustration
Let’s say we have the following linked list 1 > 2 > 3 > 4
and we want to delete the node with the value of 3
.

Initialize pointer
curr
pointing towardshead
node with value1
andprev
asNULL
. 
Iteratively move
curr
until we reach the node with the value as3
andprev
at2
. 
Point
prev
i.e.2
towardcurr>next
i.e.4
. 
Remove the
curr
node with value3
.
Linked List Removal Implementation
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int x) {
this>data = x;
this>next = NULL;
}
};
void deleteNode(Node*& head, int val) {
if (head == NULL) {
cout << "Element not present in the list\n";
return;
}
if (head>data == val) {
Node* t = head;
head = head>next;
delete (t);
return;
}
deleteNode(head>next, val);
}
void deleteiter(Node** head, int x) {
Node* temp = *head;
Node* prev = NULL;
if (temp != NULL && temp>data == x) {
*head = temp>next;
delete temp;
return;
} else {
while (temp != NULL && temp>data != x) {
prev = temp;
temp = temp>next;
}
if (temp == NULL) return;
prev>next = temp>next;
delete temp;
}
}
void printList(Node* head) {
Node* curr = head;
while (curr != NULL) {
cout << curr>data << " ";
curr = curr>next;
}
cout << "\n";
}
int main() {
Node* head = new Node(1);
head>next = new Node(2);
head>next>next = new Node(3);
head>next>next>next = new Node(4);
head>next>next>next>next = new Node(5);
printList(head);
deleteNode(head, 3);
printList(head);
deleteiter(&head, 4);
printList(head);
return 0;
}
Linked List Removal Algorithm Complexity
Time Complexity
 Average Case
To remove a node at the ith
position in the linked list, we have to visit i
nodes. So, the time complexity is of the order of O(i)
. And we have n
nodes in the linked list, so the averagecase time complexity is O(n/2)
or O(n)
. The time complexity is of the order of O(n)
.
 Best Case
The bestcase occurs when we want to delete the head of the linked list. The bestcase time complexity is O(1)
.
 Worst Case
The worstcase time complexity is O(n)
. It is the same averagecase time complexity.
Space Complexity
This algorithm’s space complexity is O(1)
in the case of iterative implementation because it doesn’t require any data structure other than temporary variables.
In the recursive implementation, the space complexity is O(n)
due to the space required by the recursive calls stack.
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedInRelated Article  Data Structure
 Circular Doubly Linked List
 Circular Linked List
 Doubly Linked List
 Linked List Insertion
 Linked List Merge Sort