Computer Science 210
Data Structures

Fall 2017, Siena College

Lab 7: Iterators and More Lists
Due: the start of your lab session on Wednesday, November 15, 2017

In this longer-than-usual lab, you will be working with iterators and linked lists more extensively. Since it's a long lab, you will also have 12 days, including a lab session, to work on it. However, you will almost certainly not finish in just the two hours of lab.

You will be assigned a partner to work with on this lab. Only one submission per group is needed.

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository iterators-lab-yourgitname for this Lab. One member of the group should follow the link to set up the repository on GitHub, then that person should email the instructor with the other group members' GitHub usernames so they can be granted access. This will allow all members of the group to clone the repository and commit and push changes to the origin on GitHub.

Please answer lab questions in the file in your group's GitHub repository. You may submit scans or legible photos of your memory diagrams, or you may create them in a drawing program. Either way, these should be included in your repository.

Iterators and Iterables

Before we get into the linked list tasks, we first take a look at some iterators.

Question 1: Draw a memory diagram of the Iterators program, showing the status inside the second call to on line 26. (10 points)

Question 2: Describe briefly the meaning of the value in the instance variable current of the VectorIterator class (in structure5), in terms of which elements of theVector have already been visited, which is going to be visited next, and how it determines if there are more elements yet to be visited. (5 points)

The Iterators example includes two custom iterators over Vectors: the VectorEvenIterator will return only the elements of the Vector from even-numbered indices, and PrefixSumIterator returns, at each step, the sum of all values up to and including the current position (try it!). The latter works only on Vectors of Integer.

Practice Program: Write another custom Vector iterator, ReverseVectorIterator, that, you guessed it, returns the values of the Vector in reverse order. Include a test of it in's main method. (10 points)

More Vector Methods

In a recent project, you developed an extension of the Vector class that included a Comparator-based sort method. We will continue in that direction for this task, creating an extension of Vector uncreatively called ExtendedVector that will include three new methods, plus a main method that tests these.

Some code for is in your repository. In that code you will find stubs of three methods:

(7 points) This method takes an int (let's call it n) as its parameter, and returns a new ExtendedVector whose contents are every nth element from the ExtendedVector on which it is called.

For the sample ExtendedVector called green in the provided main method, which has the contents

"I" "will" "not" "eat" "green" "eggs" "and" "ham"

the ExtendedVector returned by the call green.everyNth(3) should have the contents

"I" "eat" "and"
(7 points) This method takes two parameters: a value of the same type as is in the ExtendedVector and a Comparator capable of comparing elements of that type. The returned ExtendedVector should include all elements from the ExtendedVector on which it is called where the values are at least as big as the value given as the first parameter, as compared by the given Comparator.

For our ExtendedVector named green in the example, the ExtendedVector returned by the call

green.atLeast("eggs", new structure5.NaturalComparator())

should have the contents

"will" "not" "green" "eggs" "ham"
(6 points) This method takes no parameters. It simply shuffles the values in the ExtendedVector. Ideally, the shuffling should be such that every element has an equal probability to end up in every position.

Also expand the main method to do more thorough tests. You should create at least two more instances of ExtendedVector that contain two different types of data. At least one of these should be a custom class (you may reuse one from an earlier lab or project if you wish). (10 points)

Your implementations of these methods and the additional tests will be graded as a practice program.

Methods on Lists and Iterators

The ListMethods class in the provided starter code includes two methods that find the maximum value from a collection of Integer values. One takes a List<Integer> parameter, which, as we will see, can be any class that implements java.util.List and contains Integer values. The second takes an Iterator<Integer> parameter.

Practice Program: Enhance ListMethods to have similar methods (one that takes a List and one that takes an Iterator) named findSum that compute the sum of the Integer values. Include tests in main that demonstrate that your new methods work properly. An important test is to make sure it works on an empty list. (10 points)

Practice Program: Enhance ListMethods to have similar methods (one that takes a List and one that takes an Iterator) named findAverage that compute the average of the Integer values (returned as a double). Include tests in main that demonstrate that your new methods work properly. Here, you may assume at least one element is in the list, as the average of 0 items makes no sense. (10 points)

More Iterators

Earlier in this lab, you wrote a method of our ExtendedVector class that returned another ExtendedVector that contained "every nth" element from the original. Here, we are going to take that same idea and apply it to an iterator.

Practice Program: Write an iterator in a class EveryNthVectorIterator that returns every nth value. Also write a short main method that creates and populates at least two different Vectors and iterates over each with at least two different values of n. (10 points)

So considering the same example as above, if your Vector is called samIAm and contains the Strings:

"I" "will" "not" "eat" "green" "eggs" "and" "ham"

The code

  Iterator<String> iter = new EveryNthVectorIterator(samIAm, 3);
  while (iter.hasNext()) {

should print


Hint: This is very similar to the VectorEvenIterator you wrote.

Next, we'll do the same thing but for the SimpleLinkedList class.

Before proceeding, read the section of the topic notes about the iterator for the SimpleLinkedList example, and study its code to make sure you understand it. There is a copy in your repository.

Practice Program: Write implementation and test code for a new iterator that returns every nth value from the list. Procedure below. (15 points)

  1. Create another class within called SimpleListEveryNthIterator. The existing SimpleListIterator class is a good model to follow. Note that your constructor will need an extra parameter to indicate how far to skip ahead on each iteration, and that value will need to be stored in an instance variable of your iterator.
  2. Add a method to SimpleLinkedList called everyNthIterator that constructs and returns an instance of SimpleListEveryNthIterator. It should be very similar to the existing iterator method.
  3. Add code to the main method in SimpleLinkedList that tests your new iterator.

SimpleLinkedList Practice Programs

Question 3: We saw that the Java API classes ArrayList, Vector, and LinkedList all implement the java.util.List interface. If we wanted our SimpleLinkedList class to be interchangeable with those, we could also have it implement List. What methods would need to be added to our SimpleLinkedList class to satisfy the List interface? (5 points)

For the two practice programs below, you may implement the methods for both within the copy of the SimpleLinkedList example that is in your repository.

Practice Program: While it would be a significant amount of work to have SimpleLinkedList implement the entire List interface, some of the methods are not that difficult to implement. Enhance SimpleLinkedList to include the following methods: isEmpty, indexOf, lastIndexOf, and subList. Write code in the main method that tests your new methods. (25 points)

The methods of the RatioList linked list were all recursive. We can also write recursive versions of the SimpleLinkedList methods. For example, we could rewrite add as follows:

   public void add(int pos, E obj) {

        // negative positions not allowed
        if (pos < 0) {
            throw new IndexOutOfBoundsException(
              "Attempt to add at negative position " + pos);

        head = add(pos, obj, head);

    private SimpleListNode<E> add(int pos, E obj, SimpleListNode<E> startAt) {

        // if we are adding to an empty list it must be at position 0
        if ((startAt == null) && (pos != 0)) {
            throw new IndexOutOfBoundsException("Position too large for add");

        // are we adding at the front of this part?
        if (pos == 0) {
            return new SimpleListNode<E>(obj, startAt);

        // we are adding somewhere else, so let the recursion do the work
        startAt.setNext(add(pos - 1, obj,;
        return startAt;

Notice that we needed to add a private helper method that is aware of the internals of the list structure (it takes the extra parameter which is a SimpleListNode).

Practice Program: Replace the contains and get methods of SimpleLinkedList with recursive equivalents. [Good news: as accessors rather than mutators, these are substantially simpler than the add method above.] (10 points)

More Memory Diagram Practice

Consider the following program:

public class SimpleLinkedListExample {

    public static void main(String args[]) {

        SimpleLinkedList<GenericPair<Integer,String>> a = 
            new SimpleLinkedList<GenericPair<Integer,String>>();

        a.add(new GenericPair<Integer,String>(120,"Intro to Programming"));
        // draw first diagram of memory when the get method call below
        // is about to return its value
        System.out.println("Added " + a.get(0));        
        a.add(new GenericPair<Integer,String>(210,"Data Structures"));
        a.add(new GenericPair<Integer,String>(225,"Advanced Programming"));
        // find and remember the GenericPair with the longest String
        Iterator<GenericPair<Integer,String>> i = a.iterator();
        GenericPair<Integer,String> longest =;
        while (i.hasNext()) {
            GenericPair<Integer,String> pair =;
            if (pair.getSecond().length() > longest.getSecond().length()) {
                longest = pair;
                // draw second diagram of memory at this point when pair
                // refers to the (210, "Data Structures") GenericPair object

As you can see, it uses two classes from previous examples: GenericPair and SimpleLinkedList. Note: use the original SimpleLinkedList, not the one you modified for previous sections of this lab.

Question 4: Draw a complete memory diagram showing the state of objects and variables in memory at the execution point indicated by the comment near the top of the main method shown above. Include the implicit this reference for any non-static method in execution. (10 points)

Question 5: Draw a complete memory diagram showing the state of objects and variables in memory at the execution point indicated by the comment near the bottom of the main method shown above. Include the implicit this reference for any non-static method in execution. Note that this will be at the end of the second iteration of the while loop. (20 points)


Your submission requires that all required deliverables are committed and pushed to the master for your repository's origin on GitHub. That's it! If you see everything you intend to submit when you visit your repository's page on GitHub, you're set.


This assignment is worth 170 points, which are distributed as follows:

> FeatureValueScore
Q1: Iterators memory diagram 10
Q2: describe current 5
ReverseVectorIterator correctness 10
ExtendedVector everyNth correctness 7
ExtendedVector atLeast correctness 7
ExtendedVector shuffle correctness 6
ExtendedVector main method and tests 10
ListMethods findSum methods and tests 10
ListMethods findAverage methods and tests 10
EveryNthVectorIterator implementation and tests 10
SimpleListEveryNthIterator implementation and tests 15
Q3: List method list 5
SimpleLinkedList isEmpty method 3
SimpleLinkedList indexOf method 5
SimpleLinkedList lastIndexOf method 5
SimpleLinkedList subList method 7
SimpleLinkedList test code in main 5
SimpleLinkedList recursive contains method 5
SimpleLinkedList recursive get method 5
Q4: first linked list memory diagram 10
Q5: second linked list memory diagram 20
Total 170