Computer Science 210
Data Structures

Fall 2018, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

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

As you finish each step, please have your instructor initial the hard copy of this lab handout you were issued to indicate successful completion.

Names:

Learning goals:

1. To gain expertise drawing a memory diagram for a recursive data structure.
2. To learn how to implement recursive methods for an opaque recursive data structure.
3. To learn about the implementation details of iterators by implementing one for an existing class.

Submitting

As you complete each programming task, commit with a meaningful commit message and push to your group's GitHub repository for this lab.

Once all written items are initialed to indicate completion, turn in the hard copy of this lab handout you were issued.

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository for this Lab (listpractice-lab-yourgitname). One member of the group should follow the link to set up the repository on GitHub. Other group members will receive a subsequent email with a link to follow that will grant them the rights to clone the repository and commit and push changes to the origin on GitHub.

A Linked List Memory Diagram

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.

Recursive SimpleLinkedList Methods

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) {

        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 ((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
        SimpleListNode<E> newNext = add(pos - 1, obj, startAt.next());
        startAt.setNext(newNext);
        return startAt;
    }

Notice that we needed to add a private helper method that is aware of the internals of the list structure (it takes an extra parameter which is a SimpleListNode that we can use to "walk" down the structure recursively).

Your next tasks will replace a few other SimpleLinkedList methods with recursive equivalents. Please answer the lab questions first and get your answers approved before moving on to implementation. [Good news: as accessors rather than mutators, these are substantially simpler than the add method above.]

We will first work toward a recursive contains method.

Once your responses above have been approved, implement the recursive contains method in SimpleLinkedList and test cases. Test cases should include a call on an empty list, calls that find the value located in the first position, somewhere in the middle, and at the last position, and calls that do not find the value on lists of at least two different sizes.

Next, we work toward a recursive get method implementation.

In the recursive case, get method will make a recursive call where the parameters

Once your responses above have been approved, implement the recursive get method in SimpleLinkedList and test cases. Test cases should include a call on an empty list (which will throw an exception, so you can comment it out after you've verified it works), calls that find the value located in the first position of a one-element and a multi-element list, calls that find the value somewhere in the middle, a call that finds the value at the last position, and a call that tries to get a value on a list that does not contain enough elements for that to succeed (another that will throw and exception).

Iterator Practice

We looked at the idea of iterators in the context of our SimpleLinkedList, but they are typically provided by any data structure that stores a collection of elements. Let's consider this idea in the context of our old friend, the DoubleArrayList.

In order to operate correctly and efficiently, an iterator should maintain some state (in one or more instance variables) that allow it to determine if the iteration is complete and to return the next unvisited element. Think of it like a "bookmark" that remembers where to pick up on the next iteration.

Here are the steps to implement an iterator for DoubleArrayList:

• Create a new non-public class DoubleArrayListIterator in DoubleArrayList.java. This class should implement Iterator<Double>.
• Add instance variable(s) and implement the required methods. You should follow the example in the SimpleListIterator to deal with the remove method, which we do not want to bother with.
• Make DoubleArrayList implement the Iterable interface, and the required method iterator to construct and return an instance of your new DoubleArrayListIterator.
• Write a few tests to demonstrate your iterator in action, one that uses the iterator's methods directly, and one that uses them implicitly in an enhanced for loop.

Don't forget to commit and push all of your code for this lab to your group's GitHub repository.