CSC 241- Lab 4 (Due November 12, 1997)


Theme ...

Here are the objectives that are addressed by this lab.

As it has been our approach, you will copy some files and modify a List class. This class maintains a list of integers and has methods that allow for flexible addition and deletion of elements. Several of the methods use the concept of position of node. These methods take a parameter that indicates the position of the node that we wish to operate on or from. For example, if the remove method is invoked with the parameter 5, we will traverse the list, find the 6th node and remove it from the list. Position parameter needs to be between 0 and N-1, where N is the number of elements in the list. All methods that need to validate position return -1, if it is not in the range stated. They return 0 when position is appropriate.

One of the methods that I have written for this class returns the whole content of the list in a string. This method is named dump. Generally, such a component is only useful for tracing the activity of a list. In a test program, you add an element then use dump to make sure it worked correctly. The same thing after you remove an element. It is certainly an effective visual technique for seeing what you may have done wrong. You will notice that dump gets invoked after each operation in the test program for List to ensure that the right thing happens.

I will first describe one of the performance shortcomings that exists in the implementation of List and you will fix it. You will write a recursive find method that locates an element recursively. The find method will use this method to produce an answer.

Keep in mind that there may be other performance improvements that can be made and there are other methods that would be useful, however, we won't deal with them in this lab.


Create directories and copy some files

  1. cd public-html/classes/csc241
  2. cp -r ~mohammad/public-html/classes/csc241/List/ . -- don't forget the dot or the -r. This command replicates my List directory and its subdirectory in your account.
  3. To be sure that you have everything, do the following:

Compile all Java files and run the test program

  1. Use javac to compile all of the above .java files.
  2. Run the program that tests intList.

Tune intList

One of the problems with the intList is in its handling of bad positions by methods that need such a parameter. For example, when the addBefore is invoked with addBefore(10,6);, it is intended to create a new node, put 6 in it and place the node right before the 10th node in the list. If we don't have 10 nodes in the list, this method, correctly, returns -1. However, the way that it is written now, it exhaustively looks at all nodes in the list to make that determination. We consider its complexity to be O(n). With a little work, we can change its complexity to O(1) in these cases. All we need is a new variable called sizethat keeps track of the number of elements in a list. It starts as zero when we start, each time an element is successfully added to the list, size is incremented, and each time an element is removed, it is decremented. How is size going to help us? Simple, in each method that needs a position parameter, we will check to make sure position is between 0 and size-1. This also means that if position is in the correct range, we don't need to check for going past the end of the list while traversing it. Consider the current code for addBefore:

  public int addBefore(int pos, int val) {
    if (head ==null) return -1;
    if (pos == 0) {
      head = new Node(head,val);
      return 0;
    }
    // setup so that temp always points to the node before the one that
    // we want to insert before.
    Node temp;
    int last;
    for (temp=head,last=0;temp.next != null;temp=temp.next,last++)
      if (last == (pos-1)) {//found the spot to insert
        temp.next = new Node (temp.next,val);
        return 0;
      }
    return -1;
  }
      

if pos contains a position that is not in the list, it is not until for (temp=head,last=0;temp.next != null;temp=temp.next,last++) traverse the list all the way to the end that we figure out pos is invalid. Just to be sure that you understand how this for loop works I'll elaborate. temp starts at the head of the list, last starts as 0. After each cycle of the loop, temp moves to the next node and last is incremented. If you look at the code in the loop, you will notice that once the correct position is found, we add a new node to the correct position with value provided in val and return from this method. However, it is only when temp.next is equal to null, which means we have gone through the whole list, that we figure out the position provided was invalid.

Now lets suppose that we now have the following declaration for size at the top of this class and assume that it is incremented each time a new node is added and decremented when a node is removed:

private int size=0;

Notice how I can take advantage of size to check to make sure pos is valid before I start the loop. By knowing that pos is valid when the loop begins, I no longer have to check for falling off the end of the list. It is also important to notice that size must be incremented when a successful add takes place.

  public int addBefore(int pos, int val) {
    if ((pos>(size-1))||(pos<0)) return -1; //check for pos in valid range
    if (pos == 0) {
      size++;                      //was left out
      head = new Node(head,val);
      return 0;
    }
    Node temp;
    int last;
    //loop until the correct position is reached, the ';' at the
    // end of the for statement means that it is complete without
    // any statements inside it.
    for (temp=head,last=0;last != (pos-1);temp=temp.next,last++);
    temp.next = new Node (temp.next,val);
    size++;
    return 0;
  }

What you need to do

  1. Replace addBefore with this new version.
  2. Add the declaration of size as shown at the top of the class.
  3. Modify all methods that require pos to use size as I have in addBefore.
  4. size needs to be incremented in append and addAfter and decremented in the remove method.
  5. After compiling everything, you should execute the test program to make sure it still works the way it did before. remember, we didn't change behavior, we just changed implementation.
  6. Rewrite the find method recursively. What are your base cases? what should you do, if you are not at a base base?
  7. Make sure that find still works.