CSC 16 Lab 5: Linked List Basics

		       Due Tuesday 10/18


This time I'm not going to give you any code, and you should not copy
and paste anything from the web page.  You can use my sample program
"lists.java" as a guide, but CREATE YOUR OWN PROGRAM! 

1. Create a class "dcell" that represents a linked list of doubles 
   (instead of ints).

   The head and tail should be private.  You need to create a constructor,
   plus accessor methods head() and tail().

   Also create a toString function for your class - all this should be
   similar to what's in the "lists.java" program.


2. Write a method (within the dcell class) that appends one list to the
   end of the "this" list.  That is, if A represents 1-2-3 and B is
   4-5-6, then A.append(B) should change A to 1-2-3-4-5-6.

   Hint: this should be a simple modification of the "addToEnd"
   function in my program, except you are not just adding one integer
   to the end of the list, but an entire list.

3. Write a method that returns the average of all the numbers in the list.
   hint: you have already seen a function that returns the sum of the numbers

4. Write a method that returns the number of times a certain double
   appears in the list:  For example, if A is 1-3-4-3-5 then
   A.occurs(3) should return 2, because 3 appears twice in the list.

   public int occurs(double x) // returns how many x's are in list

   hint: this should be a modification of the "member" function, which
   returns true if x is in the list, and false otherwise.  

 5. Write a method - public double lastnum() - that returns the
   number at the END of the list.  If the list is null, then 
   return 0 as a default value (alternatively, you can throw an exception).
   Watch out: your loop must stop on the last cell, not when current==null!

 6. I've already written a method largest() that returns the largest number
    in a list.  My version is in the oop style.  Rewrite it in the functional
    style.  That is, the header should be
 
    public static int largest(cell A)

    Unlike the oop style, you must first check that A is not null.


(the next one will be harder ...)
7. Write a function 

   public cell doubleup()

   that CONSTRUCTS a new list that repeats each element of the "this" list.
   For example, if A is 1-2-3 then A.doubleup() should return the list
   1-1-2-2-3-3.  Note that this is a constructive function, so you should
   not change the structure of A - create a new list following the example
   of the reverse function (use an accumulator list that's initially null).


7b. Write a recursive version of the doubleup function in the static style:

    public static cell rdoubleup(cell A)

    (hint: consult the reverse list example)

8. Sometimes we want to go from a list to an array.  Write a static
   function that takes a list of doubles and returns an array containing
   the doubles in the same order.

   public static double[] arrayTolist()


9. Make a main() function (in another class) to test all the above.



EXTRA CREDIT CHALLENGE.  

   It is possible, through errors in programming, to create a loop in 
   a linked list: for example:

   A.tail.tail = A;

   None of the functions we have here will ever terminate because our "i"
   pointer will never be null!.  Write a function to determine if there
   are any cycles in a list.  hint: it's perfectly fine to test if
   two pointers A and B point to the same object with A==B.  You'll have
   to maintain a *list of pointers*.