Linked List Losing nodes after leaving recursive function

Question

struct Letter {
    char let;
    Letter *next;
}; 

Please look at the function below called addLETTERS().

int main() {
        Letter *Top = 0;
        Letter *head = 0;
        char letters = 'a';
        head = new Letter;
        Top = new Letter;

    MakeNull(head);
    MakeNull(Top);
    addLETTERS(Top, head,letters);
    return 0;
}

void MakeNull(Letter *newNode){

        newNode = new Letter;
        newNode->let = 0;
        newNode->next = 0;
}

For some odd reason when leaving this function my Linked List losses all its created nodes? Using GDB I can clearly see the function is working and adding the entire alphabet to the list. Can someone run this simple code and tell me why?

struct Letter *addLETTERS(Letter *Top, Letter *head, char& letters) {

    if(letters != 'z' + 1){
        Top = new Letter;
        Top->let = letters++;
        Top->next = head;
        head = Top;
        addLETTERS(Top,head,letters);

    }
    else {
        Top->let = '\0';
        Top->next = head;
        head = Top;
    }


    return Top;    
}

Answer 1

Here's somewhere to start:

int main() {
        Letter *Top = 0;
        Letter *head = 0;
        char letters = 'a';

    MakeNull(&head);
    MakeNull(&Top);
    addLETTERS(Top, head,letters);
    return 0;
}

void MakeNull(Letter **newNode){

        *newNode = new Letter;
        (*newNode)->let = 0;
        (*newNode)->next = 0;
}

Basically, If you do this:

void MakeNull(Letter *newNode) {
  newNode = new Letter;
  //...

...you are passing in an address, contained in the (pointer) variable 'newNode' (which is local to the function) - but then you are immediately assigning that variable a new value. Passing in the value is useless. Modifying the function's local copy of that value doesn't modify the pointer variable in the main function which you used to pass in that value.

So I modified it so that you pass in the address of the pointer variable - a 'double pointer'. That way, you can modify the contents of the pointer variable in the main function.

The same issue occurs with your 'addLetters' function: you're passing in an address (head) which you modify inside the function - but that won't modify the variable who's value you passed in.

Answer 2

well in addition what sje397 pointed out, look at the ending condition

struct Letter *addLETTERS(Letter *Top, Letter *head, char& letters) {
...
    else {
        Top->let = '\0';
        Top->next = head;
        head = Top;           <--- this will do nothing
    }

   return Top;    
}

if you want to change the argument 'head' you need to pass it as a **head

*head = Top

Answer 3

Most Importantly Thank You both Anders K and sje397 very much! I used both your examples and got it to work! Here is the functional code. GBD shows everything being passed outside of my functions and its printing out.

int main() {
    Letter *Top = 0;
    Letter *head = 0;
    char letters = 'a';
    head = new Letter;
    Top = new Letter;

    MakeNull(&head);
    MakeNull(&Top);
    addLETTERS(Top, &head,letters);
    printLinkedList(head);
    return 0;
}

void MakeNull(Letter **newNode){

    *newNode = new Letter;
    (*newNode)->let = 0;
    (*newNode)->next = 0;
}

struct Letter *addLETTERS(Letter *Top, Letter **head, char& letters) {

    if(letters != 'z' + 1){
        Top = new Letter;
        Top->let = letters++;
        Top->next = *head;
        *head = Top;
        addLETTERS(Top,head,letters);
    }

    return Top;

}

struct Letter *printLinkedList(Letter *Top){

    if(Top != 0){
    cout << Top->let << endl;
    Top = Top->next;
    printLinkedList(Top);
    }

    return Top;
}