Linked List with double pointers. Infinite loop

Question

I'm not sure why this code is causing an infinite loop. Calling push_frontLL() once doesn't cause any problems but calling it twice cause 1's to be infinitely printed.

class Node {
public:
    size_t data;
    Node* next;
    Node() {
        this->data = 0;
        this->next = nullptr;
    }
};
void push_frontLL(Node** &head, int val) {
    Node* newNode = new Node();
    newNode->data = val;
    if (head != nullptr) {
        newNode->next = *head;
    }
    head = &newNode;
}
int main() {
        Node** head = nullptr;
        
        //insert
        pushLL(head, 0);
        pushLL(head, 1);

        // print
        Node* current = *head;
        while (current != nullptr) {
            cout << current->data << " ";
            current = current->next;
        }
        return 0 ;
}

I think it has something to do with the fact push_frontLL() is over writing the previous node, but I not sure how or why it's doing that. Maybe because it uses the same identifier, newNode, twice? Just a guess. When I insert manually instead of using a function it works fine.

// insert
Node* newNode1 = new Node();
newNode1->data = 0;
if (head != nullptr) {
    newNode1->next = *head;
}
head = &newNode1;

Node* newNode2 = new Node();
newNode2->data = 1;
if (head != nullptr) {
    newNode2->next = *head;
}
head = &newNode2;

Putting the insert block into a for loop has the same effect as push_frontLL(). An infinite loop of printing the most recently added node's data.

// insert
for (size_t i = 0; i < 2; i++) {
    Node* newNode = new Node();
    newNode->data = i;
    if (head != nullptr) {
        newNode->next = *head;
    }
    head = &newNode;
}

I would like to continue using the double pointer if possible. Why is this infinite loop happening?

Answer 1

With head = &newNode; you are saving a pointer to a variable in the main scope, but since newNode is a local variable, it will be freed when the push_frontLL returns, giving any code that later relies on *head an undefined behaviour.

Your code is also mixing C and C++ practices (double pointers and pass-by-reference parameters). You should not use double pointers for this use case in C++, and do like this instead:

void push_frontLL(Node* &head, int val) {
    Node* newNode = new Node();
    newNode->data = val;
    newNode->next = head;
    head = newNode; // Don't use address of newNode
}

int main() {
    Node* head = nullptr; // Not double pointer
    
    //insert
    push_frontLL(head, 0);
    push_frontLL(head, 1);

    // print
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    return 0;
}

With a double pointer for the push_frontLL parameter -- which is what you would do in C -- it would look like this:

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

int main() {
    Node* head = nullptr;
    
    //insert
    push_frontLL(&head, 0);
    push_frontLL(&head, 1);

    // print
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    return 0;
}

But if also in the main program you want to use a double pointer (I have no clue why you would want that?), then you'll need to allocate the space for what that pointer-pointer points to -- this is all very unnatural for C++:

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

int main() {
    Node* empty = nullptr; // memory for what head points to:
    Node** head = ∅
    
    //insert
    push_frontLL(head, 0);
    push_frontLL(head, 1);

    // print
    Node* current = *head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    return 0;
}