sgdb ForwardList

I took the vector code and modified the vector to a simple forward link list data structure. In order to do link list, we need to create a "link node". In the simplest case, it is just adding one pointer which points to the next node. There are a few different ways of doing so:

• 1. adding it directly to the student class

  2. using struct as described in textbook

  3. create "has-a" node class (which is similar to "struct")

  4. create "is-a" inheritance class

#1 is definitely not a good idea. It defeat the purpose of code reuse. The studentNode will duplicate code from studentGrade.

#2 and #3 are similar. Both struct and class are supported in C++, see "struct vs class" for more detail. My preference is to use class only to simplify life (one less thing to remember). A small write-up is added for #3 approach.

In this exercise, I choose to do the #4 approach (well, just for fun). The student (aka studentGrade in code) class remains unchanged. We just add studentNode class as follows:

class studentGrade

{

friend ostream& operator<< (ostream&, const studentGrade&);

friend istream& operator>> (istream&, studentGrade&);

public:

string name;

int grade;

};

class studentNode : public studentGrade

{

public:

studentNode *next; // link to next

};

Building the link list from file now use dynamic allocations. Every student imported from the file is a new node. In our code, the new node is added to the beginning of the list. If we want append to the end, it can be easily accomplished. Furthermore, it will be a good exercise to add it to the list in the "sorted order". This is the "insertion sort" which is another subject of sorting study.

bool studentGradeDB::load(string fn)

{

ifstream fin(fn.c_str());

if (fin.fail()) return false;

while(!fin.eof()){

studentNode *sgp = new studentNode;

fin >> *sgp;

sgp->next = head; // add it to the beginning of linklist

head = sgp;

}

fin.close();

return true;

}

Note that because of inheritance, studentNode is a student. All operations are inherited by studentNode. That's why we can directly use fin >> *sgp; even though it is a studentNode.

Delete a node is an interesting exercise, not complicated, but tedious. We need to be able to anticipate all cases. I used two pointers to simplify the removal. Also, do not forget to release the deleted object.

bool studentGradeDB::remove(string name)

{

if (head==NULL) return false;

// case: remove first one

if (head->name == name){

head = head->next;

return true;

}

studentNode *ptprev = head;

studentNode *pt = ptprev->next;

while (pt != NULL)

{

if (pt->name == name) {

ptprev->next = pt->next;

delete pt;

return true;

}

ptprev = pt;

pt = pt->next;

}

return false;

}

Note:

• • By the way, there is a bug (well, at least one :-( ) in the remove function above. Can you figure it out?

• Other ways of implementing the remove function?

• How about adding another function remove an object?

  • bool studentGradeDB::remove(studentNode)

• The insertion above (inside the load) is just a simple insert-front.

  • What if we can insert new items in alphabetical order?

  • If we do that, the list is automatically sorted. (in fact, that's the insertion sort algorithm).

• What if you have doubly linked list, how would the program look like?

• Bug in the remove function: memory leak in //case: remove first one