CSC 241- Lab 4 (Due November 15th, 2002)

Theme ...

This lab will help you learn more about linked lists as well as classification. in the package intList you will partially develop a new class sortableIntList that extends an existing class intList. For this lab, you will only implement two of its helpder methods:size() and half().

Create directories and copy some files

1. cd public-html/classes/csc241
2. cp -r ~mohammad/public-html/classes/csc241/intList . -- don't forget the dot or the -r. This command replicates my intList directory and places it in your account.

Compile Java files and run the test programs

1. Use javac to compile each of the files, including the files in testList directory.
2. read test1.java and test2.java in testList and run them to see how we are testing the methods in intList.

sortableIntList

create this class in your intList directory packaging it the same way as intList and node class are. sortableIntList must extend intList and must contain the two methods that are described below:

size()

In this method, design a loop that iterates through all elements of the list starting from header_ and keeps a counter. This counter is returned and gives us the number of elements in the list.

half()

Based on size of the list, design a loop that traverses the list until it gets to the node in position size/2. A new sortableIntList is then constructed with its header_ bound to first node in the second half of the list (i.e. the node after the one at position size/2). The next_ field of the node in position size/2 is then set to null completely separating the two halves. The newly consturcted sortableIntList is returned. Current_ of both sublists should be set to their respective header_.

test your methods

write a new test program like test1.java in the testList directory and have it invoke both of these method and test them.

What to Turn In