Computer Science 210
Data Structures

Fall 2018, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

Lab 6: Introduction to Linked Lists
Due: 3:45 PM, Monday, October 29, 2018

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

You will be assigned a partner 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 practice drawing a memory diagram for a recursive data structure.
  2. To implement recursive methods for a recursive data structure.
  3. To consider the relative advantages and disadvantages of a very specific recursive data structure and a generic implementation.

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 (listintro-lab-yourgitname). 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.

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. (30 points)

Extending the RatioList

Before you take on the programming tasks for this section, look back at the existing recursive methods of the RatioList class. Notice that the pattern is the same for all of these. The base case is the one where rest is null. The recursive case "solves" the problem by calling the method recursively on rest, which is always a smaller RatioList, and then combines that result with information from the Ratio in first to get the overall answer.

The first recursive method you will add, size, follows this pattern. The method should return the number of Ratios in the RatioList on which it is called. You may assume it is called on a non-null RatioList (i.e., there is at least one Ratio already in the list).

Question 2: What is the base case and what value should be returned in that case? (4 points)

Question 3: Once you have the result of the recursive call in the recursive case, what do you need to do to transform that into the result of the original call? (4 points)

Now write the size method along with at least three test cases in the main method.

Question 4: Demonstrate your working recursive size method and tests. (10 points)

We saw in the existing code how new Ratio objects are added to the beginning of the RatioList by calling the constructor. The second new recursive method you will write, addToEnd, takes a Ratio as its only parameter and puts the given Ratio in a new RatioList node at the end of the linked list.

Big 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).

Write the recursive addToEnd method and at least three test cases. One of those cases should be adding to the end of an existing RatioList of size 1.

Question 5: Demonstrate your working recursive addToEnd method and tests. (12 points)

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.

Question 6: Describe specifically how you would convert the RatioList implementation's class header, instance variables, and constructor, to make it a general list of any data type. (5 points)

Question 7: Consider each of the remaining methods in RatioList, including the ones you just wrote. 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)

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