CSC 241- Lab 4 (Due November 10th, 2003)


Theme ...

This lab will help you learn more about linked lists as well as classification. in the package intList you will develop a new class orderedIntList that extends intList and enables us to maintain a list of value in ascending order.


Create directories and copy some files

  1. cd public-html/classes/csc241
  2. cp -r /csclass/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 .java 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.

Create the orderedIntList

The following should be used as a template in creating this new class. Note that the other methods from intList are simply inherited as well as the variables current_ and header_.


public class orderedIntList extends intList {

  public orderedIntList() {
	super();	
  }
  
  public void insert( int x ) {
      /* if list is empty || x is smaller than element_ in header_
            construct a listNode with header_ referencing it
            with x and header_ as parameters. Have Current_
            also reference this new node.  return.

         node temp=header_;
         while (temp.next_ != null && x is larger than element_ in  temp.next_)
             temp=temp.next_;

         construct a node with temp.next_ referencing it
         with x, and temp.next_. Have Current_
            also reference this new node. return.
       */
  }
  
  public void insertAtBeginning( int x )  {
        /*Do Nothing--insertAtBeginning will act as no-op for this class */  }
}

Create the testSort

Using test1.java and test2.java as models develop test programs for orderedIntList. Make sure normal as well as boundary cases are tested. Boundary cases are insertions that insert in front or at the end as the value inserted causes that to occur.

set up a orderedTest1 that first does a insertAtBeginning to attempt to insert 1 (remember 1 won't get inserted), then use insert 3,2,6,9, and 5.
Here is output from my orderedtest1.java:

java orderedtest1
Content After All Inserts: head-> 2-> 3-> 5-> 6-> 9->
The value in the current node is 5
The value in the next node is 6


What to Turn In

orderedIntList.java and the test programs.