creating a linked list with each node pointing to another linked list

Question

Hey Guys my code is supposed to create a linked list of students and for each student, it has to create a linked list of grades for that student. I cant really tell if my two linked lists are set up properly, since no grades print when i try to traverse thru the lists.

 struct Grade{
     float score;
 };

struct GradeNode{
    Grade grade;
    GradeNode *next_gnode;
};

struct StudentNode {
   string name;
   GradeNode *ghead;
   StudentNode *next_snode;
};

StudentNode* head; //head of student linked list

the function below takes input from a file and makes a node with its value along with a pointer (ghead) to a linked list of grades, Set to null at first.

void buildStudentList(string n){

StudentNode *newNode{ new StudentNode}; //initialize new Student node
StudentNode *curr; //to traverse thru Student lIst

//initialize student node
newNode->name = n;
newNode->next_snode = nullptr;

//have HEAD of THIS student's grades set to null, since there are no grades present for this student at this moment
newNode->ghead = nullptr;

//if student list is empty
if(!head){

    //make this student node the head of the list
    head = newNode;
}
else{

    //else add it to the end of the list

    curr = head;

    //traverse to the end of the list
    while(curr->next_snode){
        curr= curr->next_snode;
    }

    //make grades for this student
    buildGradeList(newNode->ghead, newNode->name);

    //assign new node to the end of the list
    curr->next_snode = newNode;

}
};

build grade list function

//parameter is Grade Head, where we will attach a grade link list to it
void buildGradeList(GradeNode *head, string n){

//NOTE: head is HEAD OF GRADE LIST

bool quit = false;
int x;

while (!quit) {

    cout<<"ENTER GRADE FOR "<<n<< ": (0 to quit)"<<endl;
    cin>>x;
    cout<<endl;

    if(x==0){
        //exit while loop and return      //when one presses 0, they go to the next student on the list!!!
        quit=true;
    }
    else{
        //append this value to head
        appendGrades(head, x);
    }
}

//return to prev function
return;
}

appends grade to linked list, head is still ghead (head of grade list for this student)

void appendGrades(GradeNode *head, int s){

//create a new node with new score value
GradeNode *new_grade = {new GradeNode};
new_grade->grade.score = s;
new_grade->next_gnode = nullptr;

//node to traverse list
GradeNode *curr;

if(!head){
    head = new_grade;
}else{

    curr=head;

    while (curr->next_gnode) {
        curr= curr->next_gnode;
    }

    curr->next_gnode = new_grade;
}
};

Would appreciate any input, guys!

Answer 1

The easiest solution to implement would be to change GradeNode * head to GradeNode *& head in the signature for buildGradeList and appendGrades functions. This will work, but I don't suggest you use it, because it misses the point of your exercise.

Your code seems mostly correct to me (I haven't run it, so I can't be sure,) apart from the one problem: when you pass the head of the grades list to those two functions, you pass it by value. This means that a copy is made of the head, and all your changes will be made to a copy, which means they don't take effect and your students' GradeNode * gheads will never actually point to anything.

Based on the mostly-correct code you have here (and based on my experience that most programmers struggle with pointers and linked lists,) I think you understand the concept of passing something by value versus passing a pointer/reference to something. However, to be able to work with pointers, you have to understand that a pointer itself is nothing but an address, i.e. a value. Therefore, when you pass a pointer into a function, you can modify the value of the object that it points to and that change will be seen by the caller, but any change you make to the pointer itself will be lost at the end of the function, because these changes were made to a copy of an address which means you don't have access to - and therefore cannot change - the original address.

This all means that when passing a pointer to a function, you cannot change where it points to. But the solution is easy.

When you want to change the value of an int variable inside a function and have the caller see the change, you pass the address of that integer to the function, in the form of an int *. So, if you want to change the value of an 'int *' variable inside a function (not the value it points to, but the value of the pointer itself,) you pass the address of that pointer to the function, in the form of an int **.

In your case, that means you have to change the signature of the two functions I mentions to these:

void buildGradeList(GradeNode **head, string n);
void appendGrades(GradeNode **head, int s);

and of course, you have to make slight modifications to the body of appendGrade as well:

...
if(!*head){
    *head = new_grade;
}else{
    curr=*head;
...

This will be correct, and this will work, and it will be right in the spirit of the original problem and your solution.

The solution I suggested at the top also works, with no change other that adding an & (called a "reference", or a little more precisely an "lvalue reference") to the function signatures because that is exactly what a "reference" is in C++. A reference is a pointer that doesn't need special syntax to work with (no * to de-reference or & to take the address of something.) This means that references are more convenient to work with, but they can't do many of the things that you do with pointers (e.g. the loop you have to find the end of the linked list is impossible to write in that form using references.)

But I want to suggest something even better. Both functions that take the head of the grades list might also change that list. So I suggest that instead of accepting a pointer to a pointer to the head of the list (or a reference to a pointer to the head,) they can always return the pointer to the head. This means that they sometimes return a new head pointer, and sometimes the same pointer that was passed to them, but they don't change the actual head pointer themselves; they return the pointer they think should be the head, and let whoever called them to decide.

The changes you need to make are as follows:

// First, change how we call buildGradeList inside buildStudentList:
newNode->ghead = buildGradeList(newNode->ghead, newNode->name);

// then, change the signature for buildGradeList:
GradeNode * buildGradeList (GradeNode * head, string n) {

// then, when you are calling appendGrades, store the value it returns in "head":
head = appendGrades(head, x);

// appendGrades will return the "head" (sometimes new, sometimes the same old one)
GradeNode * appendGrades (GradeNode *head, int s){

// just add this to the end of the appendGrades function:
return head;

That's it. You could also change the buildStudentList function to obey this design and always return the head of the students linked list (sometimes new, sometimes the same old one.) I believe this is better and more useful, specially in more complex problems/tasks you will encounter later.