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

  • 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.
  • 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 Illustration

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.

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
  • Linked List