I initially wanted you to learn about jdb which the java debugger. Debuggers are tools that enable you to trace the execution of your program. You can even step through certain routines that you suspect to be faulty. While stepping through the segment they allow you to display your variables, so you can see how a particular variable is manipulated. They are indeed a great tool. However, as I spent a little time with jdb, I decided it is not worth our lab time. May be, in one of its future versions, it will become a viable tool, but at this point, it is not.
There are three objectives that are addressed by this lab. You need to become better aquinted with linked lists. You also need to learn techniques for debugging programs that have linked lists. Lastly, you need to think about algorithm complexity.
As it has been our approach, you will copy some files and modify a class List. This class maintains a list of integers and has methods that allow for flexible addition and deletion of nodes. 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 is one that returns the whole content of the list in a string. the method is named dump. Generally, such a component is only useful for tracing the activity of the program. 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 then add a new method to List, replace, that will replace the element in a node identified by its position with a new value. That doesn't mean that there aren't other performance improvements that can be made, nor, that there aren't other methods that would be useful, it simply means that these are the ones that we will focus on for 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 performance to O(1). All we need is a new variable in this
class called sizethat keeps track of the number of elements in the
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 holds
a value 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:
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) {
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);
return 0;
}