JIYIK CN >

In this article, we will learn how to delete a node from a linked list.

Linked list deletion algorithm

Let headbe a pointer to the first node of the linked list and let tempbe the value of the node to be deleted from the linked list.

Iterative Algorithm

• Initialize pointer currto point to headfor traversing the linked list and prevset to NULLto keep track of the node before when deleting temp.
• If the node to be deleted is head, that is, temp!= NULL&& curr->data== temp, then headset to curr->nextand delete curr.
• Otherwise, do the following until we reach the node we want to delete.
  • prev=temp。
  • temp=temp->next。
• If temp== NULL, return;
• Set prev->nextto temp->next, and delete tempthe node.

Recursive Algorithm

• If head== NULL, then the linked list is empty and there is no element to be deleted. Therefore, return;
• If head->data== temp, we found the node to delete.
  • Store headin a temporary node t.
  • Set headto head->nextto remove the node.
  • Delete tand return to the earlier recursive call.
• If none of the above conditions are met, recursively call head->nexton deleteNode()to continue searching for nodes.

Linked list deletion diagram

Suppose we have the following linked list 1 -> 2 -> 3 -> 4, and we want to remove 3the node whose value is .

• Initializes a pointer to the node with values 1​​and . prevheadcurrNULL
• Move repeatedly curruntil you reach a node with values ​​of 3and . prev2
• To point to prev( ie 2) . curr->next4
• Delete the node 3whose value is curr.

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

Complexity of linked list deletion algorithm

Time Complexity

• Average situation

To delete 第 i 个a node at position in a linked list, we have to visit inodes. Therefore, the time complexity is about O(i). Moreover, there are nodes in the linked list n, so the time complexity in the average case is O(n/2)or O(n). The time complexity is about O(n).

• Best Case

The best case scenario is when we want to remove the head of a linked list. The time complexity for the best case scenario is O(1).

• Worst case scenario

The worst case time complexity is O(n). This is the same as the average case time complexity.

Space complexity

In case of iterative implementation, the space complexity of this algorithm is O(1), since it does not require any data structures except temporary variables.

In a recursive implementation, the space complexity is 1/2 due to the space required for the recursive call stack O(n).