CS 307: 12. Lists in Java
Due: Friday, November 30, 2001.
This assignment illustrates manipulation of linked lists in Java;
we will see that these are similar to lists in Scheme.
Download the file Cons.java from the class directory
(ftp.cs.utexas.edu /pub/novak/cs307/) and examine it.
This file implements a class called Cons and provides some methods
for this class. You should add your code to this file. You may
use BlueJ or another Java development environment of your choice.
The class Cons defines a data record similar to the pair
in Scheme, except that (due to strong typing) the car field
is always an integer. The file Cons.java should
compile and run as furnished; you should do this to see how it works.
Add methods to the file Cons.java as described below.
In general, these functions should work the same way as the Scheme
functions of the same name.
A test program is provided to call your programs; un-comment the
relevant lines of the test program as needed.
- An iterative version of the length function is provided
as an example.
Write a recursive version lengthr and a tail-recursive version
- member : return null if the specified integer
is not a member of the list.
- sum should find the sum of the integers in a list.
- average should find the average of the integers in a list,
returning a float.
- Write a merge sort that will sort a list of integers in ascending
order (smallest integer at the front of the list), as follows:
- Write a function merge that will merge
(combine in order) two lists that are already sorted in ascending order,
forming a single combined list. For each call with two non-empty lists,
merge should cons the smallest front element onto the
merge of the remaining elements.
- Write a function split that will make a new list
consisting of every other element of the given list.
- Write a function sort to sort a list. An empty list or a
list of one element is already sorted. For larger lists, split the list
into two halves, sort the halves, and merge the sorted halves to form the
sorted result. What is the performance (in Big O notation) of this