List Iterators

The process of going through a data structure and accessing each element of the structure is called iterating over the data structure (like traversing an array).

The Problem

We could use the list “head” pointer to access the first element, and then continue through the list by using “getnext”. The problem is that the implementation of the list - and the list “head” in particular - is private and thus we cannot access it from outside the List class.

One Solution

Provide a get_head function in the List class, which would return the value of the private list header data member. The problem with this approach, of course, is that it violates the principle of data hiding. Once we provide access to the list header, we are providing access to the internal workings of the list. Secondly, the application program must be aware of, and responsible for working with, any variation in the list organization (e.g. header nodes, circular lists, doubly lists). In fact, the application program should not even be aware of the existence of nodes (theoretically, a list could be implemented using an array).

Proper solution - List Iterator

Define a second class, called an iterator. This iterator class is defined to be a friend of the original class (the list class), which means that it has full access to all the members of the original class. The iterator class will provide methods, which can be used to traverse the original class, e.g.

class List{

friend class ListIter; // add this to the class List definition

public:

.

.

.

.

private:

.

.

.

.

};

(the method firstnode() or any variation of it should not be included in the public part of class List)
 
 
 
 
//ListIter.h
//header file for class ListIter
 
#ifndef ITER_H
#define ITER_H
 
#include "List.h"
 
class ListIter {
 public:
 ListIter(List &);
 void next();
 Type lookup();
 int done();
 private:
 Node *current;
};
 
#endif

The List Iterator class provides a constructor, which initializes the internal pointer of the class to the beginning of the list. The other methods provide the means of advancing the pointer, retrieving the information stored in the current element of the list, and testing for the end of the iteration.

 
//ListIter.cpp 
//methods for class ListIter
 
#include "ListIter.h"
 
 
ListIter::ListIter(List &l) { // a reference must be passed to the current = l.head; // constructor, if not the destructor will
} // destroy the original list.
 
 
void ListIter::next() {
 
 assert(current);
 current = current->getnext();
}
 
Type ListIter::lookup() {
 
 assert (current);
 return(current->getinfo());
 
}
 
int ListIter::done() {
 return current==0;
}

//TListIter.cpp 
//test driver for class ListIter
 
#include "ListIter.h"

main() { 
 List L;
 ListIter iter(L);
 
  for (int i = 0; i < 20; i++)
 L.insertfront(i);
 
  // while loop example
 count = 0;
 while(!iter.done()) {
 count++;
 cout << iter.lookup() << ' ';
 iter.next();
 }