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.
cd public-html/classes/csc241
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.
pwd at a Unix prompt should make that clear.
ls -R List provides a list of all files and
subdirectories and their contents staring from the List
directory. This list should look like the following:
List:
Node.java intList.java testIntList
List/testIntList:
test1.java
java test1 -- Notice how after each operation
the content of the list is dumped.
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;
}