This is an example of how an iterator can be added to the Single_list class. The Single_list class has been stripped down to only the bare essential functions to insert objects into the singly linked list.

In Project 1, it was possible to access a pointer to the first and last nodes in the linked list. These have been made private to prevent users from accessing these. Instead, the functions iterator begin() and iterator end() have been included.

Because a singly linked list can only be intelligently traversed from the first node to the last, auto-increment was implemented, but not auto-decrement. Therefore, if itr is any iterator returned by the singly linked list, you may use ++itr and itr++. The first returns an iterator to the updated location while the latter returns an iterator referencing the node originally pointed to by itr before it was incremented.

The iterator find( Type const & ) const function returns an iterator pointing to the node containing the argument if that value is found; otherwise, it returns the iterator Single_list<Type>::end().

#include <iostream>
#include "Single_list.h"
using namespace std;
using namespace ece250;

int main() {
	Single_list<int> ls;

	// Push the values 0, 1, 4, 9, 16, ..., 81 onto the singly linked list
	for ( int i = 0; i < 10; ++i ) {
		ls.push_front( i*i );
	}

	// Step through the linked list using the iterator and print the values
	for ( Single_list<int>::iterator itr = ls.begin(); itr != ls.end(); ++itr ) {
		cout << *itr << " ";
	}

	cout << endl;

	// Go through the values from 0 to 101 and determine whether or not the values
	// are in the singly linked list.
	//  - Print a 1 if it is found, and 0 otherwise:

	for ( int i = 0; i < 102; ++i ) {
		cout << ( ls.find( i ) != ls.end() );
	}

	cout << endl;

	// Step through the singly linked list and double each value
	for ( Single_list<int>::iterator itr = ls.begin(); itr != ls.end(); ++itr ) {
		*itr = 2*(*itr);
	}

	// Step through the linked list using the iterator and print the values
	for ( Single_list<int>::iterator itr = ls.begin(); itr != ls.end(); ++itr ) {
		cout << *itr << " ";
	}

	cout << endl;

	return 0;
}

The output of this program is

81 64 49 36 25 16 9 4 1 0 
110010000100000010000000010000000000100000000000010000000000000010000000000000000100000000000000000000
162 128 98 72 50 32 18 8 2 0 

The Class

The structure of the class is straight-forward: the iterator stores the address of a node. The constructor is private, so only functions within either the Single_list class or the Single_list::iterator class can call the constructor.

The public member functions include:

• Accessing the value, *itr,
• Move to the next node, ++itr and itr++,
• Determine if two iterators are referencing the same node, itr1 == itr2, and
• Determine if two iterators are referencing different nodes, itr1 != itr2.

		class iterator {
			private:
				iterator( Single_node<Type> * );
				Single_node<Type> *current;

			public:
				Type &operator*();
				iterator operator++();
				iterator operator++( int );
				bool operator==( iterator const & ) const;
				bool operator!=( iterator const & ) const;

			friend class Single_list;
		};

Internally, the operators simply compare or manipulate the addresses stored in the pointers.

The Significance?

Why is this any different from a function Single_node<Type> *head() const?

The user does not have access to the implementation—if you wanted to change the internal structure of the data structure, for example, replacing it by a linked list of arrays of values, as opposed to just linked lists of nodes storing a single value, as long as all the member functions of the iterator class were appropriately updated, the user would have no idea that the underlying implementation changed. This is not possible if the structure was exposed to the user.