C++ linked list does not delete the head node

Question

I have a very simple node class to implement the linked list (it has only data and next pointer). The function below is supposed to delete the FIRST node that has its "data" = value. the function works fine. But when I try to delete the first element (the head of the list), it does not. So, where is the problem? Here is the code

class Node{
    public:
        int data;
        Node *next;
....some other functions...

};
void deleteNode(Node *n, int value){
    cout<<"after deleting node with data = "<<value<<" : ";
    if(n->data == value){
        n = n->next;        //I guess the problem is somewhere here!
        return;
    }
    while(n){
        if(n->next->data == value){
            n->next = n->next->next;
            return;
        }
        n = n->next;
    }
}

void printTheLinkedList(Node *n){
    while(n){
        cout<<n->data<<" --> ";
        n = n->next;
    }
    cout<<"NULL"<<endl;
}


int main(){
    Node N(0);
    for(int i = 1; i < 10; i++)
        N.appendNode(i);

    printTheLinkedList(&N);
    deleteNode(&N, 3);
    printTheLinkedList(&N);
    deleteNode(&N, 0);
    printTheLinkedList(&N);


    return 0;
}

Here is the output of the code (note: 3 is deleted, but 0 is not)

0 --> 1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> NULL
0 --> 1 --> 2 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> NULL
0 --> 1 --> 2 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> NULL

Answer 1

You defined head as

Node N(0);

Thus you can not delete this node (head). You should declare head as pointer to Node

Node *N( nullptr );

In this case the function can look the following way

void deleteNode( Node * &n, int value )
{
    cout << "after deleting node with data = " << value << " : ";

    Node *current = n;
    Node *previous = nullptr;;

    while ( current && current->data != value )
    {
        previous = current;
        current = current->next;
    }

    if ( current )
    {
        if ( previous ) previous->next = current->next;
        else n = nullptr;

        delete current;
    }
}

Answer 2

First of all, you are right with your guess in your code comment. That line has to do with the issue.

There are three problems:

1. The root node cannot be deleted because it is allocated on the stack as a local variable of your main function.

2. The linked nodes need to be encapsulated in something like a linked_list container data structure. It would internally (at least) store a pointer to the head (e.g. beginning) of the linked list. If that head node gets deleted, you can just set the next pointer as the head

3. Your deletion code currently does not free the dynamically allocated nodes, so your app is leaking memory.

Since you're coding in C++ you could make use of smart pointers in order to take care of automatic deallocation.

Answer 3

You're changing the local variable n to be n->next, the head value in main doesn't actually change. Try this, which returns the new head.

Node* deleteNode(Node *n, int value){
    cout<<"after deleting node with data = "<<value<<" : ";
    if(n->data == value){
        n = n->next;        //I guess the problem is somewhere here!
        return n;
    }
    Node* root = n;
    while(n){
        if(n->next->data == value){
            n->next = n->next->next;
            return;
        }
        n = n->next;
    }
    return root;
}

Then call like:

printTheLinkedList(&N);
Node* head = deleteNode(&N, 3);
printTheLinkedList(head);
head = deleteNode(head, 0);
printTheLinkedList(head);