This website is preserved for historical and scholarly reference and is no longer actively maintained.
Assignment #3 (100 pts. total)
Due Monday, October 26 by the beginning of class.
Individual programming assignments will be accepted up to three calendar days after the program was due. There will be penalty points deducted as follows.
turned in Monday after 8 a.m.: 20 points deducted
turned in Tuesday (after midnight Monday): 40 points (total) deducted
turned in Wednesday (after midnight Tuesday): 60 points (total) deducted
turned in Thursday (after midnight Wednesday): 80 points (total) deducted
not accepted after midnight Thursday
Assignment 3: Singly Linked List Assignment.
In Section 10.4 (pages 391 - 400) Arnow and Weiss discuss self-organizing vectors.
The same principles may be applied to self-organizing lists.
The algorithm to be implemented moves the searched-for object one
position closer to the front of the list. Section 10.4.3
implements this algorithm as a "transpose" for vectors.
The interface method that will need to be changed is "contains".
An additional requirement is that "contains" search the list
(or part of list) exactly once. That is, when the method has discovered the position
of the object to be removed no further searching of the list
is necessary. In particular, do NOT start at the front of
the list again and search for the predesessor of the element to
be moved. Instead, keep references to the list elements that are
moved forward during the initial search.
You are required to reorganize the list. Do NOT change
the references to the "data" fields in the list elements. Instead,
change the contents of "nextElement" fields to accomplish the
required reorganization.
Special cases:
- The list is empty. Do not change the list.
- The list has exactly one list element. Do not change the list.
- The list has exactly two list elements. If the search is for the second element, you will need to change the reference in "head".
Other requirements:
- Name your program A3.java and submit using the handin command.
- Output is to begin with your name, your lecture section #, assignment number, date (either due or completed), and a short statement of what the problem does. All output should be carefully identified using English text. In addition to the ususal style standards (see lab #6), you are to include pre and post conditions on all methods.
- The interface for the class you construct will be
class SelfOrganizingList extends SinglyLinkedList
{
public void print ( );
public boolean contains (Object value);
public static void testDriver ( );
}
- Include a main which will call your testDriver method. The "contains" method that you write will automatically replace the "contains" method in the SinglyLinkedList class. All other methods and the instance variables of the SinglyLinkedList class will be inherited by the SelfOrganizingList class. You may use any kind of objects to store in the list (reference in the "data" field of the list element). You may prefer to use Strings because you don't have to wrap them.