# Linked List Deletion

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

• ##### Remove the `curr` node with value `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;
}
}
{
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.

## Related Article - Data Structure

• Circular Doubly Linked List
• Circular Linked List
• Doubly Linked List
• ## Related Article - Linked List

• Circular Doubly Linked List
• Circular Linked List
• Doubly Linked List