We began the evening resuming our discussion of the simple linked list from last time. If you've forgotten, you can refresh your memory by examining smallLinked.h and smallLinked.cpp. By incorporating the overloaded insertion operator (<<) into the class as a friend, we were able to overcome the limitation of access to the private "front" pointer. If you'd like to test drive this modified linked list class, download the simple driver program.
Lab Exercise. Write a generic version of the above linked list. You might want to refer to a similar exercise carried out for the stack class.
Lab Exercise. Complete the implementation of the smallLinked class. In particular, implement the copy constructor and destructor along with the remaining class methods, remove_front(), add_rear(), and remove_rear(). Note that this is the first example in which the implementation of the destructor, ~list(), is nontrivial. Since the memory needed to implement a list is dynamically allocated (with new node), then it is incumbant upon us to "clean things up" when the program is finished executing. This will require us to delete each node, one by one (a loop?).
Lab Exercise. Add code to the driver program, driver.cpp, to test the remaining methods. Finally, see if you can have the driver average the data items in the linked list.
The last lab exercise challenged us to write a program which invents a list and then calculates the average of the numbers in the list.
//File: link_driver.cpp
#include "smallLinked.h"
int main()
{
list l;
l.add_front(25);
l.add_front(12);
cout << l << endl;
int sum=0, k=0;
for (node * temp=l.front; temp
!= NULL; temp=temp->next) <===
Source of problem
{
sum += temp->data;
k++;
}
int average = sum/k;
cout << "Average=" << average << endl;
return 0;
}
But this program yields the now familiar error message:
error C2248: 'front' : cannot access private member declared in class 'list'
In order to have access to successive members of the linked list, we need to access the beginning of the list, namely front.
This is a common difficulty encountered with so-called "container classes". C++ provides a solution similar to that we used in constructing the overloaded << operator. We will define what is called an "iterator" class. It's sole purpose is to act as a companion to the list class and provide a way to iterate through the list without having illegal access to the private data members of list.
// Header File: linked.h
#include <iostream.h>
//using namespace std;
struct node
{
int data;
node *next;
};
class list
{
private:
node *front;
node *rear;
friend ostream & operator<< (ostream &, list &);
friend class ListIterator;
public:
list(); //Constructor
list(const list &); //Copy Constructor
~list(); //Destructor
// Mutators
list & add_front (const int);
list & remove_front ();
list & add_rear (const int);
list & remove_rear ();
// Accessor
bool empty() const;
};
// Companion to class list
class ListIterator
{
private:
node *current;
public:
ListIterator(const list &); //Constructor
ListIterator(const ListIterator &); //Copy
Constructor
//"next" places data from current node into
//parameter and advances current pointer
//returns true if successful
//false if at end of list
bool next(int &);
};
// Implementation File: linked.cpp
#include "linked.h"
// List IMPLEMENTATION
............
// ListIterator IMPLEMENTATION
ListIterator::ListIterator(const list & L) //Constructor
{
current = L.front;
}
ListIterator::ListIterator(const ListIterator & I) //Copy Constructor
{
current = I.current;
}
//"next" places data from current node into
//parameter and advances current pointer
//returns true if successful
//false if at end of list
bool ListIterator::next(int & number)
{
if (current==NULL)
return false;
number = current->data;
current = current->next;
return true;
}
The offending piece of code from main()
int sum=0, k=0;
for (node *temp=L.front; temp; temp=temp->next){
sum += temp->data;
k++;
}
can now be rewritten as: (see link_driver2.cpp)
int number, sum=0,
k=0;
ListIterator i(L);
while (i.next(number))
{
sum += number;
k++;
}
Lab Exercise. Implement a stack of integers using the above linked list class. (See intStack.h)