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!

The StudentNode has the name, why doesn't the GradeNode have the grade? Seems like having a separate Grade class is making it more complicated than it needs to be, or at least that there's two different approaches in the the same code. — Kingsley
– Kingsley, Commented Feb 6, 2019 at 6:00
Suggestion: generalize linked list and its nodes. A template may help here. This A) separates the list logic from the logic of the contained structures (Student doesn't know that the LinkedList holding it even exists and can concentrate on representing Students--The Single Responsibility of SOLID) and B) allows Student to contain a LinkedList<Grade> member eliminating the GradeNode class and a lot of near-duplicate code. — user4581301
– user4581301, Commented Feb 6, 2019 at 6:05
Missed a point: You can test the linked list implementation with something simple like an int, making sure that it works before adding the complication of Students and Grades. — user4581301
– user4581301, Commented Feb 6, 2019 at 6:07
@Kingsley i was going to eventually add more value for each student and was going to store them in the grade struct — Milton Pauta
– Milton Pauta, Commented Feb 6, 2019 at 6:07
@user4581301 thanks for the suggestion! will look into using templates — Milton Pauta
– Milton Pauta, Commented Feb 6, 2019 at 6:14

yzt · Accepted Answer · 2019-02-06 07:06:29Z

5

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.

edited Feb 6, 2019 at 7:06

answered Feb 6, 2019 at 6:57

yzt

9,1231 gold badge38 silver badges47 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

john Over a year ago

Wow, I hope the OP appreciates this.

john Over a year ago

This is a very common problem (passing pointers and expecting changes to the pointer to be visible outside the function). I wonder if you should write up some version of this as a specimen answer.

yzt Over a year ago

I agree that it's a very common problem, and for good reason. But I don't know what a "specimen answer" is. Could you provide a pointer?!

Milton Pauta Over a year ago

@yzt wow, thank you for this explanation ! this made a lot of sense. im gonna follow ur advice and try to have grade functions return a pointer to a head. again, thanks this has been a huge help !

yzt Over a year ago

@MiltonPauta, there are two lessons here: First is the mechanics of a pointer to pointer type and value, which every programmer should learn and be comfortable with. Second is the idea that a function that updates a value, can return the new value, instead of doing the update in-place. Both are widely applicable, but they are completely independent of each other.

|

Collectives™ on Stack Overflow

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

1 Answer 1

7 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

7 Comments

Your Answer

Sign up or log in

Post as a guest

Related