Welcome to Programming and Data Structures

An iterator only makes sense in the context of a specific collection. We can’t just make a ListIterator out of thin air - we need to get it from a list. The list class will construct the iterator for us, initializing it with the right pointer, and then give it to us.

Say we wanted to add an iterator to our LinkedList class. We would could add two functions like this:

template<typename T>
class LinkedList {
...
public:
  ListIterator<T> begin() {
      // Return an iterator pointing to the first node
      return ListIterator<T>(head);
  }

  ListIterator<T> end() {
      // Return an iterator representing "one past the end"
      return ListIterator<T>(nullptr);
  }
  ...
};

The .begin() function is supposed to return an iterator that points to the first element in the list. It does this by constructing a ListIterator initialized with the head pointer of the list. The .end() function returns an iterator that represents the position just past the last element in the list. In our implementation, if you have a pointer that is at the last node, and then advance it to the next address, it will become nullptr. So we can represent the "one past the end" position with an iterator initialized with nullptr.

Now, our loop to print out all the elements in the list is complete. myList.begin() gives us an iterator that holds a pointer to the head node. We will keep advancing that iterator until it reports that it is equal to myList.end(), which is the iterator holding nullptr.

for(ListIterator<int> it = myList.begin(); it != myList.end(); ++it) {
    cout << *it << " ";
}

template <typename T>
class ArrayList {
private:
    T* data;        // pointer to the array
    int size;       // logical size
    int capacity;   // array size
public:
    ArrayListIterator<T> begin();
    ArrayListIterator<T> end();
    ...
};