Project 1: Linked Lists and Confetti

Due: Monday, 8 Aug 2011, at 23:59:59 PST (without iterators), and Wednesday, 10 Aug 2011, at 23:59:59 PST (with iterators)

For the "second" deadline (Wednesday night), use the bundleP1b script to submit the same two files -- DoublyLinkedList12.java and vegetable.txt.

Overview

In Project 1 you will implement a doubly-linked list, including an Iterator over that list. In particular, you will implement the List12 interface. Note that you must implement a doubly-linked list -- you cannot, for instance, instead implement an array-based list.

Details

Download the List12 interface; its Javadoc can also be viewed here. Notice that List12 inherits from java.util.Iterable; hence, your implementing class must implement both the methods listed in List12.java and in the parent interface as well.

Then, create a new file called DoublyLinkedList12.java -- this will be the only Java file that you submit for credit in P1. (There will, however, be one text file associated with the Confetti simulator; see below.) DoublyLinkedList12.java should contain a class DoublyLinkedList12 that implements the interface List12. It must implement a doubly-linked list. If you implement, say, an array-based list instead, you will get 0 credit. Your source file DoublyLinkedList12.java should clearly contain your full name and student ID in a comment at the very top of the file.

You may use "dummy" head and tail nodes if you wish (I recommend this because I think it's easier), but you are not required to do so.

Your program will be graded using an automatic script. It will also be manually inspected (to make sure you actually implemented a linked list and not an array-basd list). Try to anticipate the kinds of tests we will run on your code -- how might we "stress" your code to its limit? We will do our best to find tiny bugs in your code that can result in data structure inconsistencies.

Confetti

As a visually stimulating reward for your effort in implementing your list, you will be treated to a confetti party, implemented in a set of pre-compiled Confetti classes. Note: you must run unzip Confetti.zip to extract the individual class files. You can then run the Confetti simulator by typing java Confetti. (Make sure Confetti.class, DoublyLinkedList12.class, and any other class files resulting from inner classes you implement are in the working directory.) Confetti will use your DoublyLinkedList12 to manage the confetti particles.

The Confetti simulator includes two buttons (see the screenshot below): one to add more confetti, and one to remove confetti. In the simulation window, there is some invisible "glue" on the screen which you cannot see because it is white. The glue spells out a word -- an individualized vegetable just for you. (You may not all receive unique vegetables, but there are about a dozen different choices.) The confetti particles will stick to the glue. To read the vegetable name most easily, add lots of confetti particles to the simulation (about 4000 usually does the trick), and then remove the dangling confetti. The confetti stuck to the glue will not be removed, which which render the vegetable name easily to read. Note that the Confetti simulator may crash if your linked list is not implemented properly!

Once you have identified your individualized vegetable, create a file called vegetable.txt containing your vegetable name (and no other text). This will be the second of your submission files. Your individualized vegetable is based on your CSE 12 username on ieng6.ucsd.edu; hence, make sure you log on to this machine when determining your personalized vegetable.

Submission

Submit your work using the bundleP1 script in the directory containing your DoublyLinkedList12.java and vegetable.txt files. Make sure you are logged on to ieng6.ucsd.edu using your CSE 12-specific account. As always, make sure to submit before the deadline -- the script will show you (or anyone else) no mercy!

Grading

Your submission will be graded automatically by a computer program as well as by manual inspection. Maximum score: 12 points. A maximum of 11 points will be given based on the correctness of your doubly-linked list based on our automatic testers. 8 of these points will be from the doubly-linked list without iterators, and the remaining 3 points will be for the Iterator itself. 1 additional point will be given for correctly identifying your personalized vegetable.