Linked Lists -- Part 5
Lists and Iterators

 

The original implementation of the List class had no way of traversing the list from the outside (except by printing it). The standard technique to access a list (or any collection) is an iterator.


What is an iterator?

An iterator is an object associated with a list that is capable of traversing the list -- accessing the elements one-at-a-time.

Iterators are central to the Standard Template Library. Those iterators are actually capable of changing list data. Our iterators will be much more simple -- they wil be for traversing a list, not modifying it.

Our iterators will have the following attributes and behaviors

Attribute:
a cursor into the List
Behaviors:
get the first list item
get the next list item after this one
tell if there are more items in the list


List class definition: list.h

This new definition of a List class does not overload the output operator. Instead, it declares an iterator.

// This List class implements an ordered list of integers. 
class List {
public:
   List();                          // Constructs an empty list.
   List(const List& old);           // Constructs a deep copy of old.
   ~List();                         // Deallocates all list memory.
   List& operator=(const List& rhs);// Assigns a deep copy of rhs.

   void add(int x);                 // Adds x to the list.
   void remove(int x);              // Removes one copy of x from the
                                    //   list, if x is in the list.

   bool isEmpty() const;            // Is the list empty?
   bool contains(int x) const;      // Is x a list member?

friend class ListIterator;
private:
   Node* head_;
};

Classes can declare friends. A friend can be a function or it can be a class.

A friend of a class has access to all of the members of a class -- private as well as public.


Iterator class definition: list.h

The following class iterates over all items in a list of integers. If the list is altered after the iterator is created, the iterator should be reset before using it again.

class ListIterator {
public:
   ListIterator(const List& aList);  
       // Constructs an iterator for aList. Prepares the iterator to get 
       // the first item (if it exists).
   int next();          // Next list item. ASSUME: There is a next item.
   bool more() const;   // Is there another item?
   void reset();        // Reset to the first item (if one exists).
protected:
   const Node* cursor_;
   const List& theList_;
};

There are two private members:

There is no null constructor.


Member function definitions

These go into the list.cpp file.

The constructor must use an initialization list to initialize its List reference.

ListIterator :: ListIterator(const List& aList) : theList_(aList),
                                          cursor_(aList.head_)
{ }

When the ListIterator is created, it is set to start iterating at the front of the list. This is a design decision.

void ListIterator :: reset()
{
   cursor_ = theList_.head_;
}

Pushing the cursor through the list is done via next().

int ListIterator :: next()
{
   int x = cursor_->info;
   cursor_ = cursor_->link;
   return x;
}

bool Iterator :: more() const
{
   return (cursor_ != 0);
}


An example

List grades;            // grades is an empty, ordered list
ListIterator it(aList); // it is tied to grades

grades.add(65);         
grades.add(79);         
grades.add(41);         
grades.add(98);        

it.reset();            
                        
cout << it.next() << ' '  
     << it.next();        


Going through the list is a simple loop:

for (ListIterator i(grades); i.more(); )
   cout << i.next();