Harshit Jindal Dec 26, 2022 Feb 28, 2021

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.
• ##### Recursively call `deleteNode()` on `head->next` if none of the above conditions match to keep looking for the node.

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

• ##### Remove the `curr` node with value `3`. ``````#include <bits/stdc++.h>
using namespace std;

class Node {
public:
int data;
Node* next;
Node(int x) {
this->data = x;
this->next = NULL;
}
};

{

cout << "Element not present in the list\n";
return;
}
delete (t);
return;
}
}

{

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;
}
}
{
while (curr != NULL) {
cout << curr->data << " ";
curr = curr->next;
}
cout << "\n";
}
int main()
{
head -> next = new Node(2);
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.