CS 161 recitation 13

Overview

This week we will cover iterators, and create an iterable linked list.

Lab Demo

Java provides a really cool way to iterate using a for loop, which is the foreach loop. Suppose you have an ArrayList of Strings in a variable called stringArray, you can access each element using the following statement:
for (String s: stringArray) {
    // do something with s
}
Wouldn't it be nice if we could use this syntax using other data structures. To do so, we need to make a data structure iterable, which means it provides an iterator, which is a mechanism for accessing each element in our data.

Iterators are pretty useful when dealing with data structures because of the level of abstraction that they provide. So far we've been dealing with data structures that have been pretty linear in nature or conceptualiztion. Iterating through these haven't been difficult, the user can just use a for loop to iterate through them. This won't be easy as we learn more about complex data structures. We will need to provide a way for the user to iterate through them without being complicated. That's where Iterators come in.

Let's look at the example of making an array iterable.

You will need the following file:

  • MyArrayList.java
  • An interesting thing to note about this class, is that the iterator class is an inner class: it is defined within the MyArrayList class, and therefore also has access to its instance variables.

    Lab Assignment

    To practice iterators we will create an iterable linked list. The linked list class is going to be very bare-bones, and won't provide the full complement of methods that you implemented last week. You will need the following files: Your task is to complete the class IterableLinkedList so that the foreach statement can be used with it. The implementation should closely follow that of MyArrayList, which the TA has shown.

    Your second task for this recitation is to complete the implementation of RecursiveLinkedList.java.