Lab 6 -- Introduction to Linked Lists

Fall 2017, Siena College

Home Syllabus Schedule Examples Style Guide

Lab 6: Introduction to Linked Lists
Due: the start of your lab session on Wednesday, November 1, 2017

This relatively short lab will introduce you to the idea of the linked list, a recursive data structure.

You will be assigned a partner for this lab.

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository listintro-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. At least one group member should make a clone of the repository to begin work.

Please answer lab questions in the README.md file in your group's GitHub repository.

A Recursive Data Structure

Before getting started on the lab tasks, we will look at the RatioListApplet code a bit, which is also in your repository.

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

Question 1: 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. But only if the names of all group members is placed in the comment at the top of RatioList.java!

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)
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)
Write a main method in your modified version of the RatioList class that thoroughly tests your two new methods. (4 points)

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

Submitting

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.

Grading

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

> Feature	Value	Score
Q1: `RatioList` memory diagram	10
`RatioList` `size` correctness	4
`RatioList` `addToEnd` correctness	7
`RatioList` `main` with test cases	4
Q2: how to make a generic list	10
Total	35