Delete a Node in an Elegant Way

Consider a non-empty linked list where the head points to the starting address. To delete a particular node, a simple approach is usually as follows:

void deleteNode(Node* node)
{
    if (head == node) {
        head = node->next;
        node->next = nullptr;
        return;
    }

    Node* ptr = head;
    while (ptr != nullptr) {
        if (ptr->next == node) {
            ptr->next = node->next;
            node->next = nullptr;
            return;
        }
        ptr = ptr->next;
    }
}

More Elegant Solution

Using a pointer of the pointer eliminates the need for a separate conditional statement to handle the special case of removing the first node.

void deleteNode(Node* node)
{
    Node** ptr = &head;
    while (*ptr != nullptr) {
        if (*ptr == node) {
            *ptr = (*ptr)->next;
            node->next = nullptr;
            return;
        }
        ptr = &(*ptr)->next; // the most important part
    }
}

The fundamental reason why the conditional statement was needed was that the information of the previous node could not be accessible for each loop. However, the most important part of the improved code is that the information of the previous node is accessible. As shown in the figure below, ptr does not refer directly to a node, but rather references it through the next variable of the previous node.

At first, ptr points to the address of head. This can be interpreted as pointing to the address of the next variable of a virtual node in front of head.

References

[1] Observer

[2] ch4. pointer of pointer.cpp