Deletion in Singly Linked List in C++.

Input: 3->8->1->2
Output: 3->8->2

• The deletion method takes integer data as an argument and searches the list for the node with the matching data. 
• If the head node contains the data, the node is deleted and the head is updated to point to the next node. 
• If the data is found in another node, the pointers of the preceding and subsequent nodes are modified to bypass the node to be deleted, and the node is deleted.

//C++ Program to delete the node from a linked list
#include <iostream>
using namespace std;

struct Node {
  int data;
  Node *next;
};

class SinglyLinkedList {
private:
  Node *head;

public:
  SinglyLinkedList() : head(nullptr) {}

  void insert(int data) {
    Node *newNode = new Node;
    newNode->data = data;
    newNode->next = head;
    head = newNode;
  }

  void deleteNode(int data) {
    //when list is empty
    if (head == nullptr) return;
    //deleting first node of the list
    if (head->data == data) {
      Node *temp = head;
      head = head->next;
      delete temp;
      return;
    }
    //deleting middle or last node of the list
    Node *prev = head;
    Node *curr = head->next;
    while (curr != nullptr && curr->data != data) {
      prev = curr;
      curr = curr->next;
    }
    if (curr == nullptr) return;
    prev->next = curr->next;
    delete curr;
  }

  void printList() {
    Node *temp = head;
    while (temp != nullptr) {
      cout << temp->data << " ";
      temp = temp->next;
    }
    cout << std::endl;
  }
};

int main() {
  SinglyLinkedList list;

  list.insert(10);
  list.insert(20);
  list.insert(30);
  list.insert(40);
  list.insert(50);
  list.printList();
  list.deleteNode(30);
  list.printList();
  return 0;
}

50 40 30 20 10
50 40 20 10

• Time Complexity: O(n)
• Space Complexity: O(1)