# Linked List Deletion

Harshit Jindal Feb 15, 2024

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

• ##### Else do the following until we reach the node to be deleted.
• `prev` = `temp`.
• `temp` = `temp->next`.

### Recursive Algorithm

• ##### If `head->data` == `temp` ,i.e. we have found the node to be deleted
• Store `head` in a temporary node `t`.
• Set `head` as `head->next` to remove the node.
• Delete `t` and return to the earlier recursive call.

## 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`.

## 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;
delete (t);
return;
}
}

void deleteiter(Node** head, int x) {
Node* temp = *head;
Node* prev = NULL;
if (temp != NULL && temp->data == x) {
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);
return 0;
}
``````

## Linked List Removal Algorithm Complexity

### Time Complexity

• Average Case

To remove a node at the `i-th` 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 average-case time complexity is `O(n/2)` or `O(n)`. The time complexity is of the order of `O(n)`.

• Best Case

The best-case occurs when we want to delete the head of the linked list. The best-case time complexity is `O(1)`.

• Worst Case

The worst-case time complexity is `O(n)`. It is the same average-case 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.