CODEWITHSUNDEEP
c++pointerslinked-list
Harshit Jindal
Harshit Jindal

Reputation: 621

C++ Linked List HEAD keeps resetting to NULL

I need help in understanding why my Linked List approach doesn't work as expected.

#include <iostream>
using namespace std;

class Node {
public:
    int Data;
    Node* Next;
    
    Node(int data) {
        Data = data;
        Next = NULL;
    }
};

void insertNodeAtEnd(Node* HEAD, int data) {
    Node* it = HEAD;
    if (HEAD == NULL) { HEAD = new Node(data); }
    else {
        while (it->Next != NULL) { it = it -> Next; }
        it -> Next = new Node(data);
    }
}

void printLinkedList(Node* HEAD) {
    Node* it = HEAD;
    while (it != NULL) {
        cout << it->Data << endl;
        it = it -> Next;
    }
}

int main() {
    Node* HEAD = NULL;
    // Node* HEAD = new Node(0);
    
    insertNodeAtEnd(HEAD, 5);
    insertNodeAtEnd(HEAD, 2);
    insertNodeAtEnd(HEAD, 10);
    
    printLinkedList(HEAD);
    return 0;
}

The above main() function does NOT work (ie: no output, and the HEAD keeps resetting to NULL as soon as the control leaves insertNodeAtEnd()), and I've found similar questions here on SO which explain that this is because the pointer is being passed by value, and that makes partial sense to me.
Why does it work as expected when I replace Node* HEAD = NULL; with Node* HEAD = new Node(0); in the main() function, if the pointer is being passed as value?

How are nodes getting added if I initialise HEAD like Node* HEAD = new Node(0);, but not in the case where HEAD = NULL initially? I was able to get it to work properly by using pointer to pointer but I can't understand why this approach doesn't work. I am sorry if I haven't explained my question properly, please let me know if any clarification is required.

Upvotes: 0

Views: 761

Answers (3)

GoWiser
GoWiser

Reputation: 1045

The answer has already been given by @Brotcrunsher. I am posting to help you implement a better solution, that separates the concept of a list and an element of a list, that incapsulates the methods used and that frees the resources it uses, when it goes out of scope:

#include <iostream>
using namespace std;

class Node {
public:
    int Data;
    Node* Next;

    Node(int data = 0) {
        Data = data;
        Next = nullptr;
    }
};

class List {
public:
    Node* Head = nullptr;

    void Insert(int data) {
        if (Head == nullptr)
            Head = new Node(data);
        else {
            Node* ptr;
            for (ptr = Head; ptr->Next != nullptr; ptr = ptr->Next)
                ;
            ptr->Next = new Node(data);
        }
    }

    void Print() {
        for (Node* ptr = Head; ptr != nullptr; ptr = ptr->Next)
            cout << ptr->Data << endl;
    }

    ~List() {
        Node* ptr = Head;
        while (ptr != nullptr) {
            Node* tmp = ptr;
            ptr = ptr->Next;
            delete tmp;
        }
    }
};

int main() {
    List list;
    list.Insert(5);
    list.Insert(2);
    list.Insert(10);
    list.Print();
    return 0;
}

Upvotes: 1

Brotcrunsher
Brotcrunsher

Reputation: 2254

The underlying issue can be reduced to this code:

void insertNodeAtEnd(Node* HEAD, int data) {
    //...
    if (HEAD == NULL) { HEAD = new Node(data); }
    //...
}

int main() {
    Node* HEAD = NULL;
    insertNodeAtEnd(HEAD, 5);
    //...

You seem to assume that assigning to HEAD inside insertNodeAtEnd would change the HEAD variable inside of main. This is not true. Your pointer is passed by value, so the address is copied for the function. Changing this copied variable will not change the value of HEAD inside of main.

To fix this you could pass a pointer to a pointer instead, like this:

void insertNodeAtEnd(Node** HEAD, int data) {
    //...
    if (*HEAD == NULL) { *HEAD = new Node(data); }
    //...
}

int main() {
    Node* HEAD = NULL;
    insertNodeAtEnd(&HEAD, 5);
    //...

This pointer to a pointer is still passed by value, however the pointer that it points to will be the same as the on from main.

Upvotes: 2

momolechat
momolechat

Reputation: 162

The problem come from your first insertion. You change the value of head which is reset when you quit the function. You can only change the value behind the pointer, not the pointer itself.

A solution for this would be to pass a pointer of pointer. Something like: (not tested)

void insertNodeAtEnd(Node** HEAD, int data) {
    
    if (*HEAD == NULL) { *HEAD = new Node(data); }
    else {
        Node* it = *HEAD;
        while (it->Next != NULL) { it = it -> Next; }
        it -> Next = new Node(data);
    }
}

int main() {
    Node* HEAD = NULL;
    // Node* HEAD = new Node(0);
    
    insertNodeAtEnd(&HEAD, 5);
    return 0;
}

As you don't change the pointer of pointer but only the value behind it (the actuual pointer to head) the change will be keep once you exit the function.

Upvotes: 1

Related Questions