Computer Science 210
Data Structures

Fall 2016, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

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.

More Iterators

Last week, we wrote a method of our ExtendedVector class that returned another ExtendedVector that contained "every n^th" element from the original. Here, we are going to take that same idea and apply it to an iterator.

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()) {
     System.out.println(iter.next());
  }

should print

I
eat
and

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.

1. Create another class within SimpleLinkedList.java 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

For the two practice programs below, you may implement the methods for both within the same copy of the SimpleLinkedList example.

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, startAt.next()));
        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).

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 = i.next();
        while (i.hasNext()) {
            GenericPair<Integer,String> pair = i.next();
            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
            }
        }
        System.out.println(longest);
    }
}

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.

Submitting

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

Grading

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