CpSc 210, Section 1
                             Assignment 5 
                             March 7, 2003      


Due:  Final program: Wednesday, March 26, at 11:59 p.m.  
      A partial solution must be submitted by Wednesday, March 12, at 11:59 p.m.

Assignment:  Extend Bailey's Singly Linked List to include a tail reference


Total point value of assignment:  100 points
Not accepted late.

This assignment is to be done INDIVIDUALLY.

Assignment:  Design and implement a class, ListWithTail as an extension of
     Bailey's SinglyLinkedList, which must be stored in a file named
     ListWithTail.java.  (10 point deduction for failure to name file 
     correctly!)  

Bailey's SinglyLinkedList code may be found at the "View the Local Source"
link from

http://www.mhhe.com/engcs/compsci/bailey/

or http://www.mhhe.com/javastructures

which, actually, go to the same page.

The List interface is given on pages 99-100 of Java Structures.  Your
program should include every method in the order in which the methods
are listed in the interface.  If the method in SinglyLinkedList can be
used without any changes, your code listing should include the method
as a comment:

     // public Iterator elements();  is supplied by the super class

Since we have not covered the elements() method, you should assume
that this method is supplied by the super class.  (Also, your
test driver does not need to test the elements() method.)

If you with to call the method in the super class as part of your code, 
you can do this "super." as a prefix.  For example, if my code needs
to execute addToHead for the super class, it would be coded:

     public void addToHead ( Object value )
     // post:  adds value to the beginning of list
     {
        super.addToHead ( value );
        if ( null == tail )     // the list was initially empty
           tail = head;
      }


You should make use of the code supplied by the super class whenever
doing so does not adversely affect the efficiency of your code. 
A method will be marked incorrect if the efficiency is not best possible.

An outline for the class is

     import structure.SinglyLinkedList;
     import structure.SinglyLinkedListElement;

     // constructs empty singly linked list with both head and tail references
     public class ListWithTail extends SinglyLinkedList
     {
        protected SinglyLinkedListElement tail;   // could be private

        public ListWithTail ( )
        {
           super ( );   // calls constructor of SinglyLinkedList class
           tail = null;
        }

        // and more methods

     }

Grading Rubric:

    10 pts. reasonable attempt to solve problem as assigned
    10 pts. also compiles
    10 pts. style standards (includes clarity)

            Now that we are dealing with linked lists, the comment after
            exit from "while" loops is especially important.  The comment
            on an "else" is also useful.  One point will be deducted
            for each missing comment (maximum of 10) in the code
            that you write.  (Yes, we know Bailey does not have these
            and you cannot correct his code, but you can write yours
            in this manner.)
  
            Don't forget your pre- and post-conditions.

    The following 70 points are available only for code that compiles 
    without error.   Some considerations are:

    40 pts. all code works correctly
    10 pts. growth rates of methods in ListWithTail are best possible 
            (i.e., make intelligent use of tail reference when appropriate)
     5 pts. when methods of superclass are are needed, these methods are
            called rather than code copied into new method
     5 pts. elegance of code 
     5 pts. comments are used to show methods not changed
     5 pts. evidence that your test driver (main method) systematically
            tests new code, including attention to special cases, such
            as empty list, change in head of list, change in tail of
            list, etc.