# 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 the`head`

to iterate over the linked list and`prev`

as`NULL`

to keep track of node before`temp`

when deleting it.##### If the node to be deleted is

`head`

i.e.`temp`

!=`NULL`

&&`curr->data`

==`temp`

, Set`head`

as`curr->next`

and delete`curr`

.##### Else do the following until we reach the node to be deleted.

`prev`

=`temp`

.`temp`

=`temp->next`

.

##### if

`temp`

==`NULL`

, return;##### Set

`prev->next`

as`temp->next`

and delete the`temp`

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 node`t`

. - Set
`head`

as`head->next`

to remove the node. - Delete
`t`

and return to the earlier recursive call.

- Store
##### Recursively call

`deleteNode()`

on`head->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 towards`head`

node with value`1`

and`prev`

as`NULL`

.##### Iteratively move

`curr`

until we reach the node with the value as`3`

and`prev`

at`2`

.##### Point

`prev`

i.e.`2`

toward`curr->next`

i.e.`4`

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