Assignment 5: Sentinel Lists

• Out on: March 1, 2017
• Due by: March 8, 2017 before 10:00 pm
• Collaboration: None
• Grading: Packaging 10%, Style 10% (where applicable), Testing 10% (where applicable), Performance 10% (where applicable), Functionality 60% (where applicable)

Overview

The fifth assignment is mostly about implementing the List interface. Instead of the LinkedList implementation we covered in class, you’ll write a SentinelList implementation as discussed below. Using these “sentinels” you’ll be able to write much simpler, much more concise code for almost all List operations.

Since we have the midterm next week, this assignment is shorter than normal and you do not have to write an application using the List. (Rest assured that the next assignment will be longer again!)

Problem 1: Sentinel List Implementation (90%)

Your first task for this assignment is to write an implementation of the List interface called SentinelList. Just like for the LinkedList implementation we covered in lecture, this requires that you deal with the Position and Iterator and Iterable interfaces as well.

Preface

There’s good news and bad news: The good news is that we’ll give you a working LinkedList class to start from. However, the bad news is also that we’ll give you that working LinkedList class to start from! Sounds confusing? Here’s what we mean:

It’s presumably “good” that we start you with code that “works” already, that way you should be able to make a few changes, test, make a few more changes, test again, etc. You definitely want to follow the “baby steps” philosophy again as much as you possibly can.

But it’s also “bad” that the code we give you is somewhat convoluted. The whole point of using “sentinel nodes” (see below) is to make the code much simpler and much more concise and if you stick too closely to what we give you, you can’t actually achieve that. You really must rethink the implementation from the ground up to do well! Draw pictures!

Sentinels

The LinkedList follows the basic pattern for linked lists we’ve used from the beginning of the course:

• There are references to the first and last node in the list object. These are null when there’s nothing in the list, otherwise they refer to the actual first node and the actual last node (which could be one and the same if the list has only one node).
• The nodes themselves have references to the previous and next node. The previous reference is null for the first node in the list, the next reference is null for the last node in the list. (And if there’s only one node, of course both are null.)

The result of this organization is that our code for modifying the list has to constantly check whether this, that, or the other thing is null and react accordingly. That means the code is full of conditionals where we do one thing for a null reference and another thing for a non-null reference. In other words, the code is horrible.

The idea for SentinelList is to change all that, to remove (almost) all the case distinctions around null references. To do that, we start from a simple premise, however that premise does take some getting used to:

• We always have a node at the front of the list, and we always have a node at the back of the list, but they don’t hold any data. These nodes are relevant only for the implementation, someone using the SentinelList class never gets to see them!
• Because of these “fake” nodes, the head and tail references in the list object itself are never null. That is, even an empty list (as far as the interface is concerned) will have two nodes (as far as the implementation is concerned).
• These nodes are sentinels because they “guard” the ends of the list; they are not themselves part of what the user of our List interface considers to be “the list” at any point in time.

Let this sink in for a little while, then draw some examples, starting with the empty list. As you’ll see, every insertion operation will now happen between two nodes, and there’s no longer any need to deal with null references. That’s where the big simplification comes from!

Note that if you don’t actually sit down and try this out with a piece of paper (or a whiteboard) you’ll never get it. We’re not kidding, Peter has literally stacks of pages with scribbled little list diagrams sketching the “before” and “after” situations for the various List operations. Joanne draws them on a board every semester. That’s what you want to have too before you hack the code!

Hacking

There’s not much else to say, except for this: Pay extra attention to avoiding duplicated code! Here are a few examples of what we mean by that:

• There should be one private method that validates incoming positions, you should not repeat the validation code eight separate times, once in each method that needs to perform one.
• Most of the public insertX and removeX methods should be very short indeed and rely on only a few private methods that do the actual work; those private methods should have close to zero (that is 0) case distinctions involving null references in them.

Please understand the assignment the right way: The goal is to end up with a List implementation that’s both simpler and more concise than what we gave you to start with.

No, you cannot subclass SentinelList from LinkedList! No, you cannot use a LinkedList inside your SentinelList! Your SentinelList has to stand on its own, relying only on the interfaces provided! As always, you must not change any provided code.

Testing

We’ll give you a few basic test-cases for the LinkedList class on Piazza. Please be sure to read both ListTestBase.java and LinkedListTest.java in detail before trying to modify them; we are using inheritance again.

You’ll need to add more test cases to ListTestBase and those should apply to all lists regardless of how they are implemented. You’ll also need to add a class SentinelListTest.java whose job will be obvious once you read the test cases we give you.

Be sure to test all methods and be sure to test all exceptions for error situations as well. Ideally you will make the tests better before you even start working on the SentinelList code.

Problem 2: List Reflection (10%)

This is not a programming problem; it’s a thinking and writing problem. You’ll have to write enough so we can tell that you understand the issues, but you shouldn’t write too much because that would also indicate that you don’t know what you’re doing. Please don’t ask us “How much is enough?” because there’s no right answer.

Your second task for this assignment is to write a reflection on the design we’ve come up with: the List interface itself and the Position interface clients use to “talk about” places in the data structure without “knowing” what those places really are. Here are some things you could write about, although there are probably a lot more:

• In lecture we claimed that we’re trying to support entirely different implementations of List, for example implementations using arrays of some sort instead of a bunch of Node objects. Can this actually be done using the existing interfaces? What kind of issues do you see?
• The Java library also has a List interface, but it’s rather different from ours. What are those differences and how can you explain them? (That is, assuming the Java designers are smart, capable people, why did they come up with such a different design? Why do they use integer positions for instance?)
• Is our List interface minimal in the sense that there are no operations we could leave out while still expressing what a list is? Which ones could we leave out and why? How would that impact the overall interface design? Are there operations we could leave out but shouldn’t, for example because they add a nice “symmetry”?

Your reflection should go into your README file. Feel free to take your reflection in any direction you think is useful, the points above are simply suggestions. We certainly won’t “get mad” if you tell us that our List interface is really bad, just as long as your reasoning is sound. You want to convince us that you can think and write coherently about programming independently of actually doing it!

Deliverables

You must turn in a zipped (.zip only) archive containing all source code, your README file, and any other deliverables required by the assignment. The filename should be HW##-jhed.zip with ## replaced by the 2-digit number (use leading 0s) of this assignment (see above) and jhed replaced by your Blackboard login. (For example, Peter would use HW03-pfroehl1.zip for his submission of Assignment 3.) The zip should contain no derived files whatsoever (i.e. no .class files, no .html files, etc.), but should allow building all derived files. Include a plain text README file (not README.txt or README.docx or whatnot) that briefly explains what your programs do and contains any other notes you want us to check out before grading. Your answers to written problems should be in this README file as well. Finally, make sure to include your name and email address in every file you turn in (well, in every file for which it makes sense to do so anyway)!

Grading

For reference, here is a short explanation of the grading criteria; some of the criteria don't apply to all problems, and not all of the criteria are used on all assignments.

Packaging refers to the proper organization of the stuff you hand in, following both the guidelines for Deliverables above as well as the general submission instructions for assignments.

Style refers to Java programming style, including things like consistent indentation, appropriate identifier names, useful comments, suitable javadoc documentation, etc. Many aspects of this are enforced automatically by Checkstyle when run with the configuration file available on Piazza. Style also includes proper modularization of your code (into interfaces, classes, methods, using public, protected, and private appropriately, etc.). Simple, clean, readable code is what you should be aiming for.

Testing refers to proper unit tests for all of the data structure classes you developed for this assignment, using the JUnit 4 framework as introduced in lecture. Make sure you test all (implied) axioms that you can think of and all exception conditions that are relevant.

Performance refers to how fast/with how little memory your program can produce the required results compared to other submissions.

Functionality refers to your programs being able to do what they should according to the specification given above; if the specification is ambiguous and you had to make a certain choice, defend that choice in your README file.

If your programs cannot be built you will get no points whatsoever. If your programs cannot be built without warnings using javac -Xlint:all we will take off 10% (except if you document a very good reason; no, you cannot use the @SuppressWarnings annotation either). If your programs fail miserably even once, i.e. terminate with an exception of any kind, we will take off 10% (however we'll also take those 10% off if you're trying to be "excessively smart" by wrapping your whole program into a universal try-catch).