Adventures in Data Structures Vol 8: c u l8r, iter8r
Never ceases to amaze me how much a few weeks of college can cover and how much I can forget until the night before an exam.
In these twilight hours, I’d like to take a few minutes and discuss iterators. An iterator is a facilitator object that provides an interface for working with elements in a collection. This interface is important in data structures developement, since it hides the functionality and inner workings of the container to the user (they don’t need to know about linked list or dynamic arrays or any of that stuff!)
An iterator is characterized by four functions:
initfunction to associate it with a container
hasNextwhich returns 1 if there is another element in the container
nextreturns the current element
removeremoves the element last returned by
In the end use case, we will use these iterators in code blocks like these:
What’s important to remember is that the iterator maintains a pointer to a specific element in the collection and
Next are used in combination to move that pointer forward.
remove is used, the next element in the sequence will be produced.
Iterator with a Dynamic Array
The iterator for a dynamic array will work by maintaining an index into the array representing the current location, initialized to 0.
Let’s start by defining the struct for a
dynArrayIterator and initializing it.
Notice that in our init function, we set the currentIndex = -1.
Again, this is because the first thing we’re going to do is use the
next functions which will increment index
Therefore, we want to make sure we’re not skipping the first element at index 0.
Let’s write the
next functions now.
remove function, we will make use of the fact that we already have a handy
dynArrayRemoveAt function written to take out elements at a specific index.
Note that we remove the element at the current index of the iterator and then we decrement said index.
We have to decrement in order to avoid skipping elements in the array the next time we call
Iterator with a Linked List
Let’s implement these functions on a linked list!
Whereas the dynamic array iterator kept track of an index, our linked list iterator will keep track of a current link. The struct will look like this:
The above explanation of the functions was a little confusing, but once we demonstrate how to implement this in code, it will hopefully become more clear.
Let’s start with the
hasNext function really does is check to see if the pointer
currentLink->next is equal to the back sentinel.
If it is, then there are no more elements and we return 0, otherwise we return 1.
Nice and easy :)
Let’s do another one, the
We can see here that
next moves the pointer forward in the first line, then returns whatever value is in that link.
remove function, we are going to make use of the
_removeLink function we wrote for our doubly linked lists.
We have to keep in mind that after the
remove function is called, the pointer
itr->currentLink should on the link before the link that was removed.
If we move it forward, then we will actually be skipping a link because
next always move the pointer forwards from whatever the current node is.
We use the classic little trick of defining a
temp variable and then freeing it.
itr->currentLink essentially moves backwards one link to
itr->currentLink->prev, and the handy
_removeLink function cleans up all our pointers for us.