Thoroughly Confused over Linked Lists

[Nathaniel10]

I have searched for and read through over 50 examples of linked lists. I can barely make heads or tails out of them. Some are in C, some are in Java, some use templates, most only discuss theory and display flowcharts but have few explained examples. I need serious help!

Below is the one example that I can half way understand well enough to even start asking questions about linked lists.

#include "../../std_lib_facilities.h"

struct Node {

   int num;
   Node *link;
} *p;


int main()
{

Node *root;
root = new Node;
root->num = 5;
root->link = p;
p = root;

Node *q;
for (q = p; q != NULL; q = q->link) {
    cout << q->num << endl;
}

keep_window_open();
return 0;
}

1. Why is "struct" being used instead of "class" to introduce the linked list nodes? Is it a preference for not having to declare the lines public if "class" is used?

2. I understand that "num" is the data value held in the node and that "link" is the pointer to the next node. What is "p"? The author explained that "link" points to "p" and that "p" points to the next node. I don't follow that logic. What is the need to create a pointer that is outside the list node?

3. I understand the creation of the pointer "root" and setting its value equal to a new list node. I understand the setting of the data value for the new node to 5. I understand that the old pointer value needs to be set to the address of the new node and that the pointer value in the new node needs to be set to NULL. I do NOT follow how setting the value of "link" equal to "pP and having "root" point to "link" and then having "p" take on the value of "root" accomplishes that. It seems to me that "root" ends up pointing back at itself.

4. For displaying the data contents of each node, I don't understand why a third pointer "q" needs to be created. Why can't "p" accomplish by itself what "q" does? ie. for (p != NULL; p = p->link) {cout << p->num << endl;} ?

I did some experimenting. The program still compiles and runs correctly after changing "struct" to "class" with public. So I guess that answers my first question. I also eliminated "q" in the display lines. The progran compiled and ran but did not display the value 5. So that pointer "q" is needed, but I don't understand why.

Thanks in advance for your help.

[WaltP]

Your problem is trying to understand the concept by reading code. You need to understand linked lists in general before you deal with the code. Then you will be able to see what part of the code equates with what part of the concept.

Search out a detailed generic explanation of linked lists, then go back to the code and see how the code replicates the explanation.

[mike_2000_17]

Below is the one example that I can half way understand well enough to even start asking questions about linked lists.

If that is the best example code you could find on linked-lists, then you're either very unlucky in your research, or half-blind. This code is crap.

Why is "struct" being used instead of "class" to introduce the linked list nodes? Is it a preference for not having to declare the lines public if "class" is used?

You're right. The use of struct here is just to avoid writing class Node { public: /* .. */ };.

I understand that "num" is the data value held in the node and that "link" is the pointer to the next node. What is "p"? The author explained that "link" points to "p" and that "p" points to the next node. I don't follow that logic. What is the need to create a pointer that is outside the list node?

"p" is a global variable which is a pointer to a node. Don't try to understand the reason for that variable to exist, there is none, besides the inadequacy of the programmer who wrote the code.

I do NOT follow how setting the value of "link" equal to "pP and having "root" point to "link" and then having "p" take on the value of "root" accomplishes that. It seems to me that "root" ends up pointing back at itself.

That's normal, this makes no sense.

For displaying the data contents of each node, I don't understand why a third pointer "q" needs to be created. Why can't "p" accomplish by itself what "q" does? ie.

The "q" pointer is used as an iterator through the linked-list. Whatever "p" is supposed to be in the twisted mind of the original programmer, it seems that it is supposed to be a part of the linked-list. Normally, you don't use a node pointer that is part of the list as an iterator into the list. That's why you would normally create another pointer for that.

A quick google search for "linked-list example" turns up this page as first result, it contains plenty of examples of linked-list implementations in C/C++ which make a lot more sense than the one you posted. But first, make sure you understand how a linked-list works before you start looking at code examples.

[Nathaniel10]

I worked with another program. Its code is below.

#include "../../std_lib_facilities.h"

class Student {
public:

   string name;
   double gpa;
   Student *next;
};

int main()
{
Student *head;
Student *newStudent;
Student *Student_ptr;
Student *Display_ptr;
head = NULL;

string S_name;
double S_gpa;
   for (int i = 0 ; i < 3; i++) {
      cout << "Enter Student's name." << endl;
      cin >> S_name;
      cout << "Enter Student's grade point average." << endl;
      cin >> S_gpa;

      newStudent = new Student;
      newStudent->name = S_name;
      newStudent->gpa = S_gpa;
      newStudent->next = NULL;

      if (!head) {
         head = newStudent;
      } else {
         Student_ptr = head;
            while (Student_ptr->next) {
               Student_ptr = Student_ptr->next;
               Student_ptr->next = newStudent;
            }
      }
   }

Display_ptr = head;
while (Display_ptr->next) {
   cout << Display_ptr->name << "     " << Display_ptr->gpa << endl;
   Display_ptr = Display_ptr->next;
}

keep_window_open();
return 0;
}

So. I fully understand that the data values for each node are the student's name and gpa. The address of the next node is held in the "next" variable. I understand that "head" is the pointer value to the first data node. The variable "newStudent" creates a new node. The variable "Student_ptr" traverses the list and points to the curent node at which a new student will be added to the list. The variable "Display_ptr" traverses the list and points to the current node whose data values will be printed.

This program compiles but does not run correctly. It correctly adds 3 students to the list but it does not display any. I tried to create a constructor for the list and use functions for adding to the list and displaying it but those efforts did not result in any compilable programs. The main problem was that I put "*head, *newStudent, *Stduent_ptr, and *Display_ptr" in the constructor, and the functions couldn't 'see' them. Those variables were treated as undeclared.

What should the constructor of a linked list look like?

[mike_2000_17]

Line 38 should be outside of the while loop, as so:

        while (Student_ptr->next) {
            Student_ptr = Student_ptr->next;
        }
        Student_ptr->next = newStudent;

In other words, the loop iterates to the end of the linked-list and appends the new student at the end of the list. This error was the reason why the nodes were never added to the list.

And your display loop should have this condition instead:

while (Display_ptr) {

Otherwise, it will not display the last element.

What should the constructor of a linked list look like?

Let me just put your code into a simple class to illustrate how this is done. Notice that the code is essentially your code (with the above fixes):

#include "../../std_lib_facilities.h"

class Student {
public:

   string name;
   double gpa;
   Student *next;
};


// Here is a simple class for the linked-list:
class StudentList {
  private:
    Student* head; 

  public:
    // constructor: (same as initialization code at the start of your main function)
    StudentList() {
      head = NULL;   // start with an empty list.
    };

    // function to add a node (same as within your for-loop)
    Student* AppendNewStudent(const string& aName, double aGPA) {

      Student* newStudent = new Student;
      newStudent->name = aName;
      newStudent->gpa = aGPA;
      newStudent->next = NULL;

      if (!head) {
        head = newStudent;
      } else {
        Student* Student_ptr = head;
        while (Student_ptr->next) {
          Student_ptr = Student_ptr->next;
        }
        Student_ptr->next = newStudent;
      }

      return newStudent;
    };

    // function to display the entire list (same as the last part of your main function)
    void Display() const {
      Student* Display_ptr = head;
      while (Display_ptr) {
        cout << Display_ptr->name << "     " << Display_ptr->gpa << endl;
        Display_ptr = Display_ptr->next;
      };
    };

    // IMPORTANT: You must always free the memory that you allocate!
    // This destructor will destroy the nodes of the linked-list:
    ~StudentList() {
      Student* Destroy_ptr = head;
      while (Destroy_ptr) {
        Student* tmp = Destroy_ptr;       // save the current node.
        Destroy_ptr = Destroy_ptr->next;  // move to the next node.
        delete tmp;                       // delete the current node.
      };
    };

};

// the new main function looks like this:
int main()
{
    StudentList student_list;

    string S_name;
    double S_gpa;
    for (int i = 0 ; i < 3; i++) {
        cout << "Enter Student's name." << endl;
        cin >> S_name;
        cout << "Enter Student's grade point average." << endl;
        cin >> S_gpa;

        student_list.AppendNewStudent( S_name, S_gpa );

    }

    student_list.Display();

    keep_window_open();
    return 0;
}

[Nathaniel10]

Mike,

Thank you VERY, VERY, VERY MUCH!!!!!! Not only for the 2 errors in my program, but especially for your re-write of my program! You did something that completely blew my mind! You created TWO classes!!! You have one class for the nodes, that has objects for the data values and the pointer value to the next node. Then you have a class for the list itself, that has objects and functions for traversing the list, adding nodes, deleting nodes, and displaying nodes.

In hindsight, that is completely logical. But that was not occurring to me, not would it have occurred to me for a long time. Only a handful of examples I read did that and I did not understand them at the time. Your post was a quantum leap for my understanding of linked lists. That type of post reveals that you are a serious doctoral candidate in a field that heavily uses computer programming!

[Nathaniel10]

I have added to the program. Below is the latest code. However, I need some more help

with it.

    #include "../../std_lib_facilities.h"

    class Student {
    public:

       string name;
       double gpa;
       Student *next;
    };

    class SList {
    private:

        Student *head;

    public:
        SList() {
            head = NULL;
        };

    Student* AddFirst(const string& aName, double aGPA) {

       Student* newStudent = new Student;
       newStudent->name = aName;
       newStudent->gpa = aGPA;
       newStudent->next = head;
       head = newStudent;
       return newStudent;
    };

    Student* AddLast(const string& aName, double aGPA) {

       Student* newStudent = new Student;
       newStudent->name = aName;
       newStudent->gpa = aGPA;
       newStudent->next = NULL;

       if (!head) {
          head = newStudent;
       } else {
          Student *Student_ptr = head;
          while (Student_ptr->next) {
             Student_ptr = Student_ptr->next;
          }
          Student_ptr->next = newStudent;
       }
       return newStudent;
    };

    Student* AddAfter(const string& aName, double aGPA, int k) {

       Student* newStudent = new Student;
       Student* Student_ptr;
       for (int i = 0; Student_ptr = head; i < k; i++) {
          Student_ptr = Student_ptr->next;
          if (Student_ptr == NULL) {
             cout << "\nThere are less than " << k << " students in the list." << endl;
             return;
          }
       }
       newStudent->name = aName;
       newStudent->gpa = aGPA;
       newStudent->next = Student_ptr->next;
       Student_ptr->next = new Student;

       return newStudent;
    };

    void Display() const {
       Student *Display_ptr = head;
       while (Display_ptr) {
          cout << Display_ptr->name << "     " << Display_ptr->gpa << endl;
          Display_ptr = Display_ptr->next;
       }
    };

    void Count() const {
        int c = 0;
        Student *Count_ptr = head;
        while (Count_ptr) {
           c++;
           Count_ptr = Count_ptr->next;
        }
        cout << "\nThere are " << c << " students on the list." << endl;
    };

    ~SList() {
       Student* Destroy_ptr = head;
       while (Destroy_ptr) {
          Student* tmp = Destroy_ptr;
          Destroy_ptr = Destroy_ptr->next;
          delete tmp;
       }
    };
    };

    int main()
    {
    SList student_list;

    string S_name;
    double S_gpa;
       while (S_name != "Bozo") {
          cout << "Enter Student's name.  Enter Bozo to end." << endl;
          cin >> S_name;
          if (S_name == "Bozo") {break;}
          cout << "Enter Student's grade point average." << endl;
          cin >> S_gpa;

          student_list.AddLast(S_name, S_gpa);
       }

    student_list.Display();

    student_list.Count();

    keep_window_open();
    return 0;
    }

I added a function that adds a new student to the front of the list . That version complies and runs correctly. I added a count function. That version also complies and runs correctly. Then I added a function that adds a student in the middle of the list. That version does not compile and is shown above.

The compile error is that in the for loop of the "AddAfter()" function a closing parenthesis, ")", is expected instead of a semicolon, ";", after the parameter "k". I have little idea why this is occurring. I have read about something called 'a type limitation'. I think it means that in a for loop you can't have one than data type in the parentheses. I guess int and char would violate that rule. I have a pointer and an int in the for loop in question. How should the "AddAfter" function be written?

[mike_2000_17]

In a for-loop, you must have two semi-colon (not one, not three, two!). The first slot is for initializing statements, the second slot is for a condition (logic expression), and the last slot is for a per-iteration operation (executed at the end of an iteration, before evaluating the condition).

The first and last slot can contain multiple expressions or declarations, but you separate them with a comma. In other words, you can have a for-loop like this for example:

int i, j;
for( i = 0, j = 1 ; j < N ; ++i, ++j ) {
  /* .. */
};

The problem with declaring multiple variables in the initializing statement is that C/C++ allows this type of syntax in normal code:

int i, j;  // notice the comma separation.

Whenever a type appears first, the compiler interprets this as a variable declaration (possibly also a function declaration), and then, if a comma appears after one variable declaration, then the compiler assumes the next thing will be another variable declaration of the same type. This means that you can write this:

for(int i = 0, j = 1; j < N; ++i, ++j) {
  /* .. */
};

But not this:

for(int i = 0, double f = 1.0; i < N; ++i) { /* */ };

because the compile will reject the second declaration just like it would if it appeared elsewhere like this:

int i, double f;  // ERROR

So, the basic rule for the first slot in the for-loop is that you can either have multiple statements (separated by commas) where none is a declaration, or you can have a single declaration statement with the same rules as when writing a single declaration statement anywhere else (meaning that you can declare multiple variables, separated by commas, but each having the same type). So, I guess that is what you read about as being a "type limitation" of the declarations in a for-loop. It is simply a rather unfortunate consequence of the comma-separated multiple-variable declaration syntax.

In your case, with the AddAfter function, you declare a pointer Student_ptr which is declared outside the loop because it will be used after the loop is done. It doesn't really make sense to initialize it in the for-loop statement, because it is declared prior to it. The general rule in C++ is to initialize variables when they are declared, e.g. type varname = value;, and to declare variables only when and where they are needed (meaning, don't declare a bunch of variables at the start of a function, and then give them initial values later in the function, just declare them where they are first assigned a meaningful value). These guidelines are designed to make it clear to anyone reading your code what your variables are, what value they hold, how long they live (or where are they useful), etc. It is just cleaner and easier to understand.

So, the corrected version of your AddAfter function is as follows:

Student* AddAfter(const string& aName, double aGPA, int k) {
   Student* newStudent = new Student;
   Student* Student_ptr = head;
   for (int i = 0; i < k; i++) {
      Student_ptr = Student_ptr->next;
      if (Student_ptr == NULL) {
         cout << "\nThere are less than " << k << " students in the list." << endl;
         return;
      }
   }
   newStudent->name = aName;
   newStudent->gpa = aGPA;
   newStudent->next = Student_ptr->next;
   Student_ptr->next = newStudent;         //notice, you had a typo here.
   return newStudent;
};

You did something that completely blew my mind! You created TWO classes!!!

Well, my library has hundreds of classes. Creating classes is the bread-and-butter of programming in C++, most classes are really small, some are larger, but the point is that they are the building blocks of the code. So, of course, create as many as you feel necessary. Very simply put, the idea is: one task == one class. In this case, one task is to hold the information for one node, and one task is to manage and maintain the linked-list.

Your post was a quantum leap for my understanding of linked lists.

Glad that I could be the cosmic ray that caused a beneficial single event upset in your brain.

[Nathaniel10]

Mike,

Thank you very much for the explanation of the format of the for loop statement. I had never learned about the two semi-colon rule.

I have not had time to update the program with your corrections. I am trying to include a function to delete a specific node. I will try to have something by tomorrow.

[Nathaniel10]

Well. I have tried to add a delete function to remove a node from my linked list. It is not working. I recognize that the parts of the function are: 1) input the student name to be deleted, 2) traverse the list searching for the name, 3) if the name is found, then delete the node and change the pointer value of the prior node, 4) if the name is not found, then give a message to the effect. I haven't been able to successfully do that. My code is below. It complies and runs but outputs that the student name is not found when it should be found and deleted. Please show me what the delete function should look like. (In the main function, I have used several if statements rather than a switch statement. There was an error in my switch statement that I did not want to search for right now. My focus is on the delete function.)

#include "../../std_lib_facilities.h"

class Student {
public:

   string name;
   double gpa;
   Student *next;
};

class SList {
private:

    Student *head;

public:
    SList() {
        head = NULL;
    };

Student* AddFirst(const string& aName, double aGPA) {

   Student* newStudent = new Student;
   newStudent->name = aName;
   newStudent->gpa = aGPA;
   newStudent->next = head;
   head = newStudent;
   return newStudent;
};

Student* AddLast(const string& aName, double aGPA) {

   Student* newStudent = new Student;
   newStudent->name = aName;
   newStudent->gpa = aGPA;
   newStudent->next = NULL;

   if (!head) {
      head = newStudent;
   } else {
      Student *Student_ptr = head;
      while (Student_ptr->next) {
         Student_ptr = Student_ptr->next;
      }
      Student_ptr->next = newStudent;
   }
   return newStudent;
};

Student* AddAfter(const string& aName, double aGPA, int k) {

   Student* newStudent = new Student;
   Student* Student_ptr = head;
   for (int i = 0; i < k; i++) {
      Student_ptr = Student_ptr->next;
      if (Student_ptr == NULL) {
         cout << "\nThere are less than " << k << " students in the list." << endl;
      }
   }
   newStudent->name = aName;
   newStudent->gpa = aGPA;
   newStudent->next = Student_ptr->next;
   Student_ptr->next = newStudent;

   return newStudent;
};

Student* Delete(const string& aName) {

   Student* Find_ptr = head;
   Student* Student_ptr = head;
   bool found = false;
   while (Student_ptr) {
      if (Student_ptr->name == aName) {
         Find_ptr = Student_ptr->next;
         delete Student_ptr;
         found = true;
      } else {
         Student_ptr->next = Find_ptr->next;
      }
      if (found == false) {
         cout << "\nThe student " << aName << " is not found." << endl;
         break;
      }
   }
   return 0;
};

void Display() const {
   Student *Display_ptr = head;
   while (Display_ptr) {
      cout << Display_ptr->name << "     " << Display_ptr->gpa << endl;
      Display_ptr = Display_ptr->next;
   }
};

void Count() const {
    int c = 0;
    Student *Count_ptr = head;
    while (Count_ptr) {
       c++;
       Count_ptr = Count_ptr->next;
    }
    cout << "\nThere are " << c << " students on the list." << endl;
};

~SList() {
   Student* Destroy_ptr = head;
   while (Destroy_ptr) {
      Student* tmp = Destroy_ptr;
      Destroy_ptr = Destroy_ptr->next;
      delete tmp;
   }
};
};

int main()
{
SList student_list;
char select = '0';

while (select != '7') {
cout << "Choose your desired operation.";
cout << "\nEnter a 1 to add a student to the end of the list.";
cout << "\nEnter a 2 to add a student to the start of the list.";
cout << "\nEnter a 3 to add a student to some other point in the list."; 
cout << "\nEnter a 4 to delete a student from the list."; 
cout << "\nEnter a 5 to display the list.";
cout << "\nEnter a 6 to see a count of the list items.";
cout << "\nEnter a 7 to exit the program" << endl;
cin >> select;

if (select == '1') {
   string S_name;
   double S_gpa;
      cout << "Enter Student's name." << endl;
      cin >> S_name;
      cout << "Enter Student's grade point average." << endl;
      cin >> S_gpa;

      student_list.AddLast(S_name, S_gpa);
}

if (select == '2') {
   string S_name;
   double S_gpa;
      cout << "Enter Student's name." << endl;
      cin >> S_name;
      cout << "Enter Student's grade point average." << endl;
      cin >> S_gpa;

      student_list.AddFirst(S_name, S_gpa);
}

if (select == '3') {
   int k;
   cout << "Enter the position number." << endl;
   cin >> k;
   string S_name;
   double S_gpa;
      cout << "Enter Student's name." << endl;
      cin >> S_name;
      if (S_name == "Bozo") {break;}
      cout << "Enter Student's grade point average." << endl;
      cin >> S_gpa;

      student_list.AddAfter(S_name, S_gpa, k);
}

if (select == '4') {
   string S_name;
      cout << "Enter Student's name." << endl;
      cin >> S_name;

      student_list.Delete(S_name);
}

if (select == '5') {
   student_list.Display();
}

if (select == '6') {
   student_list.Count();
}

if (select == '7') {
   keep_window_open();
}
}
return 0;
}

[Nathaniel10]

I re-wrote the delete function using a different example. That function now compiles and runs correctly. My almost final code for this singly linked list is as follows. Constructive comments are eagerly welcomed.

#include "../../std_lib_facilities.h"

class Student {
public:

   string name;
   double gpa;
   Student *next;
};

class SList {
private:

    Student *head;

public:
    SList() {
        head = NULL;
    };

Student* AddFirst(const string& aName, double aGPA) {

   Student* newStudent = new Student;
   newStudent->name = aName;
   newStudent->gpa = aGPA;
   newStudent->next = head;
   head = newStudent;
   return newStudent;
};

Student* AddLast(const string& aName, double aGPA) {

   Student* newStudent = new Student;
   newStudent->name = aName;
   newStudent->gpa = aGPA;
   newStudent->next = NULL;

   if (!head) {
      head = newStudent;
   } else {
      Student *Student_ptr = head;
      while (Student_ptr->next) {
         Student_ptr = Student_ptr->next;
      }
      Student_ptr->next = newStudent;
   }
   return newStudent;
};

Student* AddAfter(const string& aName, double aGPA, int k) {

   Student* newStudent = new Student;
   Student* Student_ptr = head;
   for (int i = 0; i < k; i++) {
      Student_ptr = Student_ptr->next;
      if (Student_ptr == NULL) {
         cout << "\nThere are less than " << k << " students in the list." << endl;
      }
   }
   newStudent->name = aName;
   newStudent->gpa = aGPA;
   newStudent->next = Student_ptr->next;
   Student_ptr->next = newStudent;

   return newStudent;
};

Student* Delete(const string& aName) {

   Student* Previous_ptr = NULL;
   Student* Find_ptr = head;
   for (Find_ptr = head; Find_ptr != NULL; Previous_ptr = Find_ptr, Find_ptr = Find_ptr->next) {
      if (Find_ptr->name == aName) {
         if (Previous_ptr == NULL) {
            Find_ptr = Find_ptr->next;
         } else {
            Previous_ptr->next = Find_ptr->next;
         }
         delete Find_ptr;
         cout << "\nThe student " << aName << " has been successfully deleted from the list." << endl;
         return 0;
      }
   }
   cout << "\nThe student " << aName << " is not found." << endl;
   return 0;
};

void Display() const {
   Student *Display_ptr = head;
   while (Display_ptr) {
      cout << Display_ptr->name << "     " << Display_ptr->gpa << endl;
      Display_ptr = Display_ptr->next;
   }
};

void Count() const {
    int c = 0;
    Student *Count_ptr = head;
    while (Count_ptr) {
       c++;
       Count_ptr = Count_ptr->next;
    }
    cout << "\nThere are " << c << " students on the list." << endl;
};

~SList() {
   Student* Destroy_ptr = head;
   while (Destroy_ptr) {
      Student* tmp = Destroy_ptr;
      Destroy_ptr = Destroy_ptr->next;
      delete tmp;
   }
};
};

int main()
{
SList student_list;
char select = '0';

while (select != '7') {
cout << "Choose your desired operation.";
cout << "\nEnter a 1 to add a student to the end of the list.";
cout << "\nEnter a 2 to add a student to the start of the list.";
cout << "\nEnter a 3 to add a student to some other point in the list."; 
cout << "\nEnter a 4 to delete a student from the list."; 
cout << "\nEnter a 5 to display the list.";
cout << "\nEnter a 6 to see a count of the list items.";
cout << "\nEnter a 7 to exit the program" << endl;
cin >> select;

if (select == '1') {
   string S_name;
   double S_gpa;
      cout << "Enter Student's name." << endl;
      cin >> S_name;
      cout << "Enter Student's grade point average." << endl;
      cin >> S_gpa;

      student_list.AddLast(S_name, S_gpa);
}

if (select == '2') {
   string S_name;
   double S_gpa;
      cout << "Enter Student's name." << endl;
      cin >> S_name;
      cout << "Enter Student's grade point average." << endl;
      cin >> S_gpa;

      student_list.AddFirst(S_name, S_gpa);
}

if (select == '3') {
   int k;
   cout << "Enter the position number." << endl;
   cin >> k;
   string S_name;
   double S_gpa;
      cout << "Enter Student's name." << endl;
      cin >> S_name;
      if (S_name == "Bozo") {break;}
      cout << "Enter Student's grade point average." << endl;
      cin >> S_gpa;

      student_list.AddAfter(S_name, S_gpa, k);
}

if (select == '4') {
   string S_name;
      cout << "Enter Student's name." << endl;
      cin >> S_name;

      student_list.Delete(S_name);
}

if (select == '5') {
   student_list.Display();
}

if (select == '6') {
   student_list.Count();
}

if (select == '7') {
   keep_window_open();
}
}
return 0;
}

[raptr_dflo]

Hi Nathaniel, excellent work over all. (Sorry to be jumping in here, but that's how it works some times!) Line 75 in your Delete() method is almost certainly not what you meant (though it looke like line 77 is good). What does it mean if Previous_ptr is NULL, and what do you really want to do in that case? Also, it doesn't hurt anything as-is, but if you're not returning anything of value from your Delete() method, consider declaring it as void Delete(...) instead of Student * Delete(...), and using an empty return statement (at line 81, the one at line 85 could be eliminated entirely). Otherwise, looking good! :)

[Nathaniel10]

Raptr,

Thank you very much for the flattering words. I cannot take much credit though because it was Mike_2000_17 who explained it so very clearly that I could really understand what was going on in a linked list.

You are right about return type for the delete function. I did not realize that the construction of Student* [function name()] implied that a return value was expected. Changing it to void [function name()] did eliminate the need for a return statement.

You are also right about line 75 above. I tried to delete the first node of the list and got a memory error. I had not tested the program thoroughly before posting it. When Previous_ptr is NULL it means that we are dealing with the first node in the list. When we delete that node, we want the head node or root node to point to the address of the, formerly, second node in the list. So the right hand side of that equation should be Find_ptr->next. I am having trouble with the left hand side. I think the LHS should be the variable head but that still gives me a memory error. I can't see how to set the root pointer equal to the address of the new first node in the list. I tried Find_ptr->head but I get a compile error that head is not a member of the class Student.

[mike_2000_17]

Your AddAfter function is somewhat problematic. In the case where k is beyond the length of the list, you print an error message and keep on going. There is one major problem with that. Because Student_ptr is NULL, whatever happens to execute afterwards will likely crash, either you get on to the next iteration and try to get the value of Student_ptr->next which will cause a crash, or you get to the code after the loop and get a crash then. So, one naive solution would be to simply return from the function at that point (inside the if-statement). However, this will cause a memory leak because you fail to add the new node to the list (because you have no valid place to put it) but you have already created that node (with new) and thus, will never be able to delete it. So, you could delete that new node before returning, but a much simpler solution is to just create the new node after the loop, since you don't need it before finishing the loop anyways. As so:

Student* AddAfter(const string& aName, double aGPA, int k) {
   Student* Student_ptr = head;
   for (int i = 0; i < k; i++) {
      Student_ptr = Student_ptr->next;
      if (Student_ptr == NULL) {
         cout << "\nThere are less than " << k << " students in the list." << endl;
         return NULL;
      }
   }
   Student* newStudent = new Student;
   newStudent->name = aName;
   newStudent->gpa = aGPA;
   newStudent->next = Student_ptr->next;
   Student_ptr->next = newStudent;
   return newStudent;
};

This is a general principle of error-handling, you need to make sure that you report and recover from an error in a clean way (not leaving leaked memory and not leaving the program (or object) in a crippled or corrupt state such that the program can recover from the error). There are various level to which you can accomplish this, we usually talk about weak exception safety, strong exception safety and no-throw exception safety. Basically, the weak level means that the state of the object (or program) will still be valid (not corrupt) after an error (or exception) has occurred. The strong level means that if an error occurs, the object or program will be left in the state that it was in before the failed operation was attempted (i.e. succeed, or fail and roll-back). Finally, the no-throw level just means that the operation is guaranteed never to fail (no error can occur).

On a slightly higher level, you should know that the preferred method for reporting such errors in C++ is the use of exceptions. Exceptions in C++ are a way to branch out of the normal execution path (a.k.a. the "good path") in order to report an error. This method is very flexible and will help you to make those errors recoverable, cleanly and safely. Throwing an exception will automatically roll-back the construction of any local objects, will automatically unwind the call-stack backwards in time (moving from callee to caller), until a try-block is encountered and the exception caught. I encourage you to look up the subject. Another related issue is that if you are creating a class like a linked-list that could be used in different contexts, it may not always be appropriate to print a message to cout (e.g. for non-console applications, cout might not make sense), so you generally shouldn't use it within your class members. So, this is how you would typically implement your AddAfter function:

Student* AddAfter(const string& aName, double aGPA, int k) {
   Student* Student_ptr = head;
   for (int i = 0; i < k; i++) {
      Student_ptr = Student_ptr->next;
      if (Student_ptr == NULL)
         throw std::out_of_range("Cannot add Student to the list! Out-of-range!");
   }
   Student* newStudent = new Student;
   newStudent->name = aName;
   newStudent->gpa = aGPA;
   newStudent->next = Student_ptr->next;
   Student_ptr->next = newStudent;
   return newStudent;
};

Another general advice is to avoid repeating the same code all the time. In this case, you have several places where you have code like this:

Student* newStudent = new Student;
newStudent->name = aName;
newStudent->gpa = aGPA;
newStudent->next = head;

You should consider lumping this inside one function, for example, you could use a factory function as a static member for the nodes:

class Student {
public:
   string name;
   double gpa;
   Student *next;

   static Student* Create(const string& aName, double aGPA, Student* aNext) {
     Student* result = new Student;
     result->name = aName;
     result->gpa = aGPA;
     result->next = aNext;
     return result;
   };
};

Then, you can replace all your node-creation blocks with this:

Student* newStudent = Student::Create(aName, aGPA, head);  // or whatever is the appropriate 'next' pointer.

You might also consider using a meaningful constructor / destructor for your Student class:

class Student {
public:
   string name;
   double gpa;
   Student *next;

   Student(const string& aName, double aGPA, Student* aNext = NULL) :
           name(aName), gpa(aGPA), next(aNext)  //use this, it's called an 'initialization list'.
   { 
   };

   ~Student() {
     delete next; // delete the next node.
   };
};

And now, you can replace all your node-creation blocks with this:

Student* newStudent = new Student(aName, aGPA, head);  // or whatever is the appropriate 'next' pointer.

Furthermore, with a destructor for the nodes like I did above, you can reduce your SList's destructor to simply this:

~SList() {
  delete head;  // the destructor of head will take care of deleting the next pointer and so on so forth.
};

As for your Delete function, I believe you meant the line 75 to be head = Find_ptr->next; because if the previous pointer is NULL, it means that Find_ptr is at the head (which means the head pointer needs to be reset). But, additionally, with my destructor, you need to prevent the next node (which will remain in the list) from being deleted. To accomplish this, you just have to set it to NULL before deleting the Find_ptr node, as so:

Find_ptr->next = NULL;
delete Find_ptr;

instead of just delete Find_ptr;.

But, overall, great work! Looking from the start of this thread, it is clear that you are learning fast! And that's why I stepped it up a bit with the comments and tricks that I gave above.

[Nathaniel10]

Thank you very much for your advice and help with this thread, Mike. For the past week I have not been able to code much. Things got busy with my job and life in general. I am teaching myself C++ part-time.

I have Stroustrup's book "Programming Principles and Practice Using C++". Its Chapter 5 deals with the error handling issues you raised. Your example is very staightforward. I found Stroustrup's examples of "try, catch, throw" to be fairly complicated and involved creating new classes for each type of error to be caught and exception to be thrown.

In hindsight, your suggestion to have a class for the students is obvious. A class for the nodes, a class for the data contained in the nodes, and a class for the list makes all the sense in the world. But there are not many (free) examples of linked lists that show your approach. I am appreciating more and more why IT managers complain of the lack of good programmers.

I tried to correct a memory error (unhandled exception) in the Delete function. I eventually found that the following code except for the line before delete Find_ptr. When I comment it out, the list member gets deleted as desired. Otherwise, I get a memory error. My experiments suggested that the original code was trying to delete the node after the desired one as well, so I moved the delete command outside of the for loop. I am not sure it is correct but the named student gets deleted and the unnamed students remain intact.

void Delete(const string& aName) {

Student* Previous_ptr = NULL;
Student* Find_ptr = head;
int ind = 0;
for (Find_ptr = head; Find_ptr != NULL; Previous_ptr = Find_ptr, Find_ptr = Find_ptr->next) {
  if (Find_ptr->name == aName) {
      if (Previous_ptr == NULL) {
         head = Find_ptr->next;
      } else {
            Previous_ptr->next = Find_ptr->next;
      }
  ind++;
  }
  }
  if (ind == 1) {
     Find_ptr->next = NULL;
     delete Find_ptr;
     cout << "\nThe student " << aName << " has been successfully deleted from the list." << endl;
  } else { 
     cout << "\nThe student " << aName << " is not found." << endl;
  }
};

I also learned a new thing about scope in the switch statement. I was getting a "transfer of control bypasses initialization" error when I tried to use a switch statement in my Main section instead of if statements. I learned that the S_name and S_gpa variables in each case were the problem. They remained in scope in the next case. It was explained to me that enclosing the case in brace brackets would limit the scope of the local variable to just that case and it would not affect the next case.

I think I have a sound understanding of the singly linked list. I am moving on the doubly linked lists. I will incorporate your suggestions on 3 classes and exception throws into that program. I am looking forward to your instructive comments on it.

[mike_2000_17]

Glad you appreciate my help.

In the Delete function you just posted. you are missing a break; statement between lines 13 and 14. Once you find the matching name in the list, you need to break out of the for-loop.

And yes, the scoping within a switch-statement carries throughout the cases. Think of it this way, scopes equal opening and closing curly braces. And, for switch-statements, don't forget the break; statement after each case (otherwise, the subsequent case will be executed as well). Put simply, switch-statements are weird, I don't like them very much, I think the syntax is awkward, but that's just my opinion (thankfully, switch-statements are rarely needed, at least, not when you know better ways).

[Nathaniel10]

I was able to get started on the doubly linked list. I completed the function to add a node at the top of the list and to display it from the bottom upward. The code so far is below.

#include "../../std_lib_facilities.h"

class Student {
public:

   string name;
   double gpa;
   Student *next;
   Student *prev;

/*
   Student(const string& aName, double aGPA, Student* aNext = NULL) : {
      name(aName), gpa(aGPA), next(aNext) //use this, it's called an 'initialization list'.
   }

   static Student* Create(const string& aName, double aGPA, Student* aNext) {
     Student* result = new Student;
     result->name = aName;
     result->gpa = aGPA;
     result->next = aNext;
     return result;
   };
*/
};

class SList {
private:

    Student *head;
    Student *tail;

public:
    SList() {
        head = NULL;
        tail = NULL;
    };

Student* AddFirst(const string& aName, double aGPA) {

   Student* newStudent = new Student;
   newStudent->name = aName;
   newStudent->gpa = aGPA;
   newStudent->next = NULL;
   newStudent->prev = NULL;

   if (head == NULL) {
      head = tail = newStudent;
   } else {
      newStudent->next = head;
      head->prev = newStudent;
      head = newStudent;
   }
   return newStudent;
};

...

void Display() const {
   int c = 0;
   Student *Display_ptr = tail;
   while (Display_ptr) {
      cout << Display_ptr->name << "     " << Display_ptr->gpa << endl;
      c++;
      Display_ptr = Display_ptr->prev;
   }
   if (c == 0) {cout << "\nThere are no students on the list to display." << endl;}
};

The above code compiles and runs correctly, displying students in the correct reverse order. It was more challenging than I expected, mostly because I don't really see why it matters whether or not the list is empty when inserting at the top of the list. It didn't matter with the singly linked list.

As I understand the doubly linked list, the 'next' pointer points to the next student in the list, the same as in the singly linked list. The main difference is the 'previous' pointer which should always point to the head of the list when adding at the top.

In writing this, I have just realized that there are 2 other pointers; head and tail. The tail always points to the last student. But this is NULL when the list is empty and is the first student when it is added. I think that is why the if statement is needed; to change the tail pointer value from NULL to the first student in the list. The tail pointer doesn't exist in the singly linked list.

I am not able to work on this more until Wednesday.