Due: November 10th @ 10:00 pm Although you should start and work on it to help you prepare for the exam.
Purpose:
Practice designing cyclic structures, and using mutation, loops, ArrayLists, and sorting.
Programming Problem 1: (Linked.java)
Below a class diagram for a cyclic structure that represents doubly-linked lists (lists that are linked both forwards and backwards).
+-----------------------+ | MutableList<X> | +=======================+ | DoubleList<X> head |---+ | DoubleList<X> tail |---+ +-----------------------+ | | +----------------+ | V +-----------------------+ | DoubleList<X> |<--+ +=======================+ | | DoubleList<X> prev |---+ | DoubleList<X> next |---/ +-----------+-----------+ / \ +-+-+ | +------------------+-----------------+ | | | +-----------+ +-----------+ +-----------+ | Head<X> | | Tail<X> | | Node<X> | +===========+ +===========+ +===========+ +-----------+ +-----------+ | X data | +-----------+The idea is that our list (MutableList) contains links for the head and the tail of the list, so we can add elements at the front or back, and since every Node with data has a prev and next field, we can easily add elements in the middle as well.The only trick is hooking up the references correctly, and testing.
How do we go about adding/removing elements without getting spaghetti? Well, we can add a Node after the head, or before the tail quite easily. Below is a nother (amazing) drawing of the situation after we add a new element.
Turn the diagram into class defintions. DoubleList should be an abstract class, but the others should all be concrete.
Head, Tail, and Node all inherit the prev and next (link) fields... for Head and Tail, initialize them to null (remember super(...);? Just make sure it's the first statement in your constructors);
We'll deal with MutableList in a bit; create the class according to the diagram, but leave out the constructor for now.
Design methods setPrev and setNext in the DoubleList class that assign/set/modify the corresponding fields (each takes a DoubleList<X>).
- Create a no argument constructor for MutableList that initializes the head and tail fields into an initial cycle, terminated by null in either direction. Here's what the instance should look like after the constructor is run:
+-------------+ | MutableList | +=============+ +--| head | | +-------------+ | | tail |--+ | +-------------+ | | | V V +----------+ +----------+ | Head |<--+ +-->| Tail | +==========+ | | +==========+ null <--| prev | +---)---| prev | +----------+ | +----------+ | next |-------+ | next |--> null +----------+ +----------+Use the set methods to link the two instances.
+-------------+ | MutableList | +=============+ +-------------| head | | +-------------+ | | tail |-------------+ | +-------------+ | | | V V +----------+ +----------+ +----------+ | Head |<--+ +-->| Node |<--+ +-->| Tail | +==========+ | | +==========+ | | +==========+ null <--| prev | +---)---| prev | +---)---| prev | +----------+ | +----------+ | +----------+ | next |-------+ | next |-------+ | next |--> null +----------+ +----------+ +----------+ | data |--+ +----------+ | [...]
If this looks confusing, work the addition and removal on paper. Draw the arrows, and realize what has to change toupdate the links.
- Design four methods together (so that you can test them all), the first two will go in the DoubleList class, and the other two into the MutableList class:
- The void method insertAfter that adds a Node with the given X after this DoubleList
- The method removeNext that removes the Node that is after this DoubleList, and returns its data (X). Think about what has to happen to the links in order to leave the Node out.
- The void method push that inserts the given X at the front of this MutableList
- The method removeFirst that removes (and returns) the X at the front of this MutableList.
Test these methods by building a list of Strings, then taking them out.
- Again you'll design four methods together, but this time we work on the back (not the front) of the list:
- The void method insertBefore that adds a Node with the given X before this DoubleList
- The method removePrev that removes the Node that is before this DoubleList, and returns its data (X). Think about what has to happen to the links in order to leave the Node out.
- The void method enqueue that inserts the given X at the back of this MutableList
- The method removeLast that removes (and returns) the X at the back of this MutableList.
Test these methods similar to the others... make sure that data is added and removed in the correct order.
Design a method forwardString for all the classes (MutableList, DoubleList, Head, Tail, and Node) that returns the data in the list as a String from front to back, with spaces in between.
Use structural recursion... do not use a loop, or helper methods (e.g., nothing like isTail()).Hint: Start at the Head, end at the Tail.
Note that any Java object (say obj) can be converted to a String simply by adding it to the empty-string:
""+objDesign a method backwardString for all the classes (MutableList, DoubleList, Head, Tail, and Node) that returns the data in the list as a String from back to front, with spaces in between.
Hint: Start at the Tail, end at the Head.
Programming Problem 2: (SpongeLoops.java)
Convert your SpongeBob program from the last homework to use Loops instead of recursive methods, and fix anything you couldn't get working. You are free to use which-ever type of loop you like... but I suggest you practice each type (while and for).
Convert all your purpose statements (you have them, right?!) into JavaDoc comments (/** ... */). Use the Ecllipse Project menu to generate your JavaDocs. Add as much info as you want, and you can use HTML markup to add italics, bold, or teletype fonts. Take it easy on the blinking and marquee though ;-)
Programming Problem 3: (Selection.java)
Review the Selection Sort problem from Lab 9.
- Complete the Selection Sort algorithm for ArrayLists of Integers, sorted in ascending order.
- Abstract your selection Sort method over the ordering using a function-interface.
/** Represents a comparison operator */ interface IComp<X>{ /** Is A 'lessthan' B? */ public boolean comp(X a, X b); }That means your selection sort method should take an IComp, and select the least element according to it, then swap it into place, and continue.- Implement classes for sorting a list of Doubles in both ascending and descending order and test your method thoroughly.