Computer Science 210
Data Structures

Fall 2016, Siena College

Lab 6: Practice with Lists
Due: 10:00 AM, Wednesday, October 26, 2016

This week's lab will give you some practice with iterators, writing more methods for Vectors, and recursive data structures.

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 "lab6.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 "lab6.pdf" before you submit it.

Iterators and Iterables

Before we get into the linked list tasks, we first take a look at a topic that will become much more relevant with our more advanced data structures: iterators.

Read the topic notes linked from the schedule page and look at the examples before proceeding.

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

Question 2: Describe briefly the meaning of the value in the instance variable current of the VectorIterator class, 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

Last week, 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 the starter package you downloaded at the beginning of this lab. 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.

You should 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 last week's lab if you wish). (10 points)

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

Memory Diagram

Consider this main method that uses the RatioList and Ratio classes from the RatioListApplet example.

    public static void main(String args[]) {

        RatioList rats = new RatioList(new Ratio(7, 9), null);
        rats = new RatioList(new Ratio(3, 4), rats);
        rats = new RatioList(new Ratio(1, 10), rats);

        Ratio theSum = rats.getSum();

Question 3: Draw a memory diagram, along the lines of the one we drew in class, for the program above at the point in its execution just before the getSum method at the base case of the recursion returns. You need not draw the constructors for each Ratio and RatioList that gets created, but the memory associated with all objects in existence and all methods in execution should be shown. (10 points)

Extending the RatioList

The extensions to RatioList will be graded as practice programs.

  1. Write a recursive method size of class RatioList that returns the number of Ratios in a RatioList. You may assume it is called on a non-null RatioList (i.e., there is at least one Ratio already in the list). (4 points)
  2. Write a recursive method addToEnd of class RatioList that takes a Ratio as its only parameter and puts the given Ratio in a new RatioList node at the end of the linked list. Hint: recursively call addToEnd on the rest of each RatioList until you find the one with a null rest, and construct a new RatioList to replace that null rest. You may assume it is called on a non-null RatioList (i.e., there is at least one Ratio already in the list). (7 points)
  3. Write a main method in your modified version of the RatioList class that thoroughly tests your two new methods. (4 points)

Question 4: Earlier in the semester, we studied a series of examples DoublePair, ObjectPair, and GenericPair showing how specific code (dealing in this case with only a pair of double values), can be generalized. Describe in some detail how you would convert the RatioList implementation to a general list of any data type. Which of the methods would remain nearly unchanged? Which methods would not be possible in a generic implementation (i.e., they have an assumption that we have Ratio objects in our list)? Which could be implemented with an appropriate extra parameter (hint: a Comparator)? (10 points)


Before 10:00 AM, Wednesday, October 26, 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 "Lab6". Don't forget to check your programming assignment programs for compliance with the Style Guide for CSIS 210 Programs


This assignment is worth 90 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
Q3: RatioList memory diagram 10
RatioList size correctness 4
RatioList addToEnd correctness 7
RatioList main with test cases 4
Q4: how to make a generic list 10
Total 90