Linked List Deletion

1. Linked List Removal Algorithm
2. Linked List Removal Illustration
3. Linked List Removal Implementation
4. 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

Recursive Algorithm

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