C++ Doubly Linked List: Deleting a Node (Efficient Algorithm with Explanation)

void deleteNode(Node** head, int data) {\n if (head == NULL) { // Check if the list is empty\n printf("List is empty.\n");\n return;\n }\n\n Node current = head; // Create a pointer to the current node\n Node prevNode = NULL; // Create a pointer to the previous node\n\n while (current->data != data) { // Traverse the list until the node with the given data is found\n if (current->next == *head) { // If the end of the list is reached and the node is not found\n printf("Element %d not found in the list.\n", data);\n return;\n }\n prevNode = current; // Update the previous node pointer\n current = current->next; // Move to the next node\n }\n\n if (current->next == *head && prevNode == NULL) { // If the node to be deleted is the only node in the list\n *head = NULL; // Set the head to NULL\n free(current); // Free the memory occupied by the node\n return;\n }\n\n if (current == *head) { // If the node to be deleted is the head node\n prevNode = (*head)->prev; // Update the previous node pointer\n *head = (*head)->next; // Set the head to the next node\n prevNode->next = *head; // Update the next pointer of the previous node to the new head\n (*head)->prev = prevNode; // Update the previous pointer of the new head to the previous node\n free(current); // Free the memory occupied by the node\n } else if (current->next == *head) { // If the node to be deleted is the last node\n prevNode->next = *head; // Set the next pointer of the previous node to the head\n (head)->prev = prevNode; // Set the previous pointer of the head to the previous node\n free(current); // Free the memory occupied by the node\n } else { // If the node to be deleted is in the middle of the list\n Node temp = current->next; // Create a temporary pointer to the next node\n prevNode->next = temp; // Update the next pointer of the previous node to the next node\n temp->prev = prevNode; // Update the previous pointer of the next node to the previous node\n free(current); // Free the memory occupied by the node\n }\n}\n\nThis function is used to delete a node with a given data value from a doubly linked list. It takes a double pointer to the head of the list and the data value as input.\n\nThe function first checks if the list is empty. If it is, it prints an error message and returns.\n\nThen, it initializes two pointers: "current" points to the head of the list, and "prevNode" is set to NULL.\n\nThe function then enters a while loop that traverses the list until the node with the given data value is found. If the end of the list is reached and the node is not found, it prints an error message and returns.\n\nInside the loop, the function updates the "prevNode" pointer to the current node and moves to the next node.\n\nAfter finding the node to be deleted, the function checks three cases:\n\n1. If the node to be deleted is the only node in the list, it sets the head pointer to NULL, frees the memory occupied by the node, and returns.\n\n2. If the node to be deleted is the head node, it updates the "prevNode" pointer to the previous node, sets the head pointer to the next node, updates the next pointer of the previous node to the new head, updates the previous pointer of the new head to the previous node, frees the memory occupied by the node, and returns.\n\n3. If the node to be deleted is the last node, it updates the next pointer of the previous node to the head, updates the previous pointer of the head to the previous node, frees the memory occupied by the node, and returns.\n\n4. If the node to be deleted is in the middle of the list, it creates a temporary pointer to the next node, updates the next pointer of the previous node to the next node, updates the previous pointer of the next node to the previous node, frees the memory occupied by the node, and returns.