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.

Contribute
DelftStack is a collective effort contributed by software geeks like you. If you like the article and would like to contribute to DelftStack by writing paid articles, you can check the write for us page.

## Related Article - Data Structure

• Convert Binary Tree to Binary Search Tree
• Binary Search Tree Iterative Insert
• ## Related Article - Linked List

• Binary Search Tree