The Iterator Definitions:

At the bottom of the list header file, we place the class definitions for the iterator classes we need.

  
//CHAR_SL_LIST Forward Iterator
class CHARSLLISTFIter{
  public:
    CHARSLLISTFIter(CHAR_SLLIST& fsl) : sl(fsl), p(fsl.head) {;};
    ~CHARSLLISTFIter(){};
    //
    void operator++();
    CHAR_SL_CELL* operator()() const;
    operator const void*() const;
  private:
    CHAR_SLLIST& sl;
    CHAR_SL_CELL* p;
  };

//CHAR_DL_LIST Forward Iterator  
class CHARDLLISTFIter{
  public:
    CHARDLLISTFIter(CHAR_DLLIST& fsl) : sl(fsl), p(fsl.head) {;};
    ~CHARDLLISTFIter(){};
    //
    void operator++();
    CHAR_DL_CELL* operator()() const;
    operator const void*() const;
  private:
    CHAR_DLLIST& sl;
    CHAR_DL_CELL* p;
  };

//CHAR_DL_LIST Backward Iterator  
class CHARDLLISTBIter{
  public:
    CHARDLLISTBIter(CHAR_DLLIST& fsl) : sl(fsl), p(fsl.end) {;};
    ~CHARDLLISTBIter(){};
    //
    void operator--();
    CHAR_DL_CELL* operator()() const;
    operator const void*() const;
  private:
    CHAR_DLLIST& sl;
    CHAR_DL_CELL* p;
  };

Notice that these have a very special syntax. The forward iterators implement an overloaded + + operator to move through the list from the head forward by grabbing the next pointer. The backward iterators implement the overloaded - - operator by moving through the list backwards from the tail by grabbing the previous pointer. Note we only build backward iterators in the doubley linked lists where previous pointer information is available. Similar constructions can be built for circular linked lists. The backward iterator code is organized as follows:

Private Iterator Elements:

     CHAR_DLLIST& sl;
     CHAR_DL_CELL* p;

We grab a reference to the list we want to move through with the iterator and we use the element p to store the previous pointer.

Constructor:

   
     CHARDLLISTBIter(CHAR_DLLIST& fsl) : sl(fsl), p(fsl.end) {;};

Note the constructor uses inline initialization to set the sl reference and the p previous pointer.

Destructor:

    
     ~CHARDLLISTBIter(){};

There is nothing to destroy, so the destructor is empty.

Increment Operator:

     void operator--();

The implementation of the overloaded - - operator is straightforward: we set p to be the non-NULL value of the previous pointer if possible or set to NULL if not. This NULL value is our test to stop iteration.

void CHARDLLISTBIter::operator--()
{
  if(p!=NULL){
    if(p->previous!=NULL){
      p = p->previous;
      }
    else
      p = NULL;
    }
}

Evaluation Operator:

     CHAR_DL_CELL* operator()() const;

The evaluation operator gets the value of the previous pointer. Now the overloaded - - operator sets the p pointer, but this function returns the value of p.

CHAR_DL_CELL* CHARDLLISTBIter::operator()() const
{
  if(p!=NULL)
    return(p);
}

Boolean Test Operator:

     operator const void*() const;

This is the strangest operator to implement. Look carefully at this code: this is our test for the pointer p to be NULL. If p is NULL, we are at the head of the list and we should stop. So in that case, we return a 0 cast to void*. If we still have a nonNULL address, we return a 1 cast to void*.

CHARDLLISTBIter::operator const void*() const
{
  if(p==NULL) return (const void *)0;
  else return (const void*)1;
}

Now consider a standard for loop:

for(i=0; i>=0; --i)
  {
  //code
  }

This can be written more abstractly as

for(start of variable to iterate; 
    test to see if we are done; 
    decrement iterator)
  {
  //code
  }

To use the iterator, we mimic this abstract for loop as follows: we assume we have a CHAR_DLLIST object T. We construct a CHARDLLISTBIter object with CHARDLLISTBIter it(T). This furnishes the iterator initialization step. Then we must supply an iteration termination test which here is given by the boolean it. This returns a boolean true or false depending on whether we are at the head of the list. Finally, we decrement the list with -it.

for(start of variable to iterate == CHARDLLISTBIter it(T); 
    test to see if we are done  == it; 
    decrement iterator == --it)
  {
  //code
  }

This gives us the iterator code

for( CHARDLLISTBIter it(T); it; --it)
  {
  //code
  }