An iterator is an object that allows you to traverse a list. You can observe their usage in container classes within the C++ Standard Library such as <vector> and <list>. A Linked list is a container class. Thus, our implementation of a linked list should also include the concept iterators.
Like Nodes, other container objects could also have an iterator. To avoid naming conflict, iterators can be nested within the list class.
There are two types of iterator. An iterator and a const_iterator. An iterator allows changes to the objects being referred to while a const_iterator does not. Thus, we need both.
Once our list is created, we will be able to go through the list using iterator objects.
For the list class, iterators should have the following
- operators to advance to the next piece of data in the linked list. (++) If the list is doubly linked, operators to advance to the previous piece of data (--)
- The dereference operator (*) to access the data stored.
- operators to compare two iterators to see if they are pointing at the same data object (not just the same data value, but the same actual instance of the object)
- assignment operator
When thinking about iterators, the important concept is that an iterator lets us go through our list one data item at a time. It is similar in nature to the loop counter that we use to go through an array. While you may view it as being similar to a node pointer, it is not the same. To the user of the list, there is no such thing as a node. They only have iterators. This is really important to remember.