Computer Science 523
Advanced Programming

Summer 2014, The College of Saint Rose

Home     Syllabus     Schedule     Examples     Style Guide

This week, you will gain some experience working with linked lists.

You may work alone or in a group of 2 or 3 on this lab. Only one submission per group is needed.

Getting Set Up

To get your BlueJ environment set up for this week's lab assignment, start BlueJ and choose "New Project" from the "Project" menu. Navigate to your folder for this course and choose the name "Lab9" (no spaces) for the project.

Create a document where you will record your answers to the lecture assignment and lab questions. If you use plain text, call it "lab9.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 "lab9.pdf" before you submit it.

Lecture Assignment Questions

We will usually discuss these questions at the start of class on the lab due date, so no credit can be earned for late submissions of lecture assignment questions.

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>(501,"Algorithms"));
        // 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>(502,"Architecture"));
        a.add(new GenericPair<Integer,String>(507,"S/W Eng"));
        
        // 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 (502, "Architecture") GenericPair object
            }
        }
        System.out.println(longest);
    }
}

As you can see, it uses two classes from previous examples: GenericPair and 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).

Submitting

Before 4:00 PM, Thursday, July 31, 2014, submit your lab for grading. There are two things you need to do to complete the submission: (i) Copy your file with the answers to the lecture assignment and 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. (ii) Upload a copy of your lab (a .7z or .zip file containing your project directory) using Submission Box under assignment "Lab9".

Grading

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