Computer Science 210
Data Structures

Fall 2016, Siena College

Lab 7: More Linked Lists
Due: 10:00 AM, Wednesday, November 2, 2016

We continue this week looking more closely at iterators and linked lists and their implementations. You will be writing a whole lot of mostly small classes and short methods, then drawing some in-depth memory diagrams. All code will be graded as practice programs.

You may work alone or with a partner on this lab. Only one submission per group is needed.

Getting Set Up

Download and extract the starter project that includes code you will need to use and modify for this lab.

Create a document where you will record your answers to the lab questions. If you use plain text, call it "lab7.txt". If it's a Word document, you can call it whatever you'd like, but when you submit, be sure you convert it to a PDF document "lab7.pdf" before you submit it.

Inheritance, Abstract Classes, and Interfaces

This is not a part of the lab assignment, but is placed here as a reminder: there is a Lecture 21 Assignment on the lecture page with some zyBook tasks. Everyone should complete those (not just one person per group) in your own zyBook by Monday.

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 we 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 named findSum that compute the sum of the Integer values. Include tests in main that demonstrate that your new methods work properly. (10 points)

Practice Program: Enhance ListMethods to have similar methods 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. (10 points)

More Iterators

Last week, we 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 last week, 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 last week.

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 the starter package for this lab.

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 1: 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 same copy of the SimpleLinkedList example.

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 2: 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 3: 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)


Before 10:00 AM, Wednesday, November 2, 2016, submit your lab for grading. There are two things to do to complete the submission: (i) Copy your file with the answers to the lab questions into your project directory. Be sure to use the correct file name. If you prepared your answers in Word, export to a PDF file and submit that. and (ii) upload a copy of your lab (a .7z or .zip file containing your project directory) to Blackboard under "Lab7". Don't forget to check your programming assignment programs for compliance with the Style Guide for CSIS 210 Programs


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

> FeatureValueScore
ListMethods findSum methods and tests 10
ListMethods findAverage methods and tests 10
EveryNthVectorIterator implementation and tests 10
SimpleListEveryNthIterator implementation and tests 15
Lab Question 1 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
Lab Question 2: first memory diagram 10
Lab Question 3: second memory diagram 20
Total 115