Summary: In this lab, you will practice fiddling with an implementation of a LinkedList in Java by iterating over a list and removing all instances of a particular element.

Preparation

private ListNode<AnyType> header;

The class weiss.nonstandard.ListNode has just two member variables:

public AnyType element;
public ListNode<AnyType> next;

The current implementation of remove only removes the first instance of an item in a list. It does so by first calling findPrevious to get an iterator situated at the node immediately before the item. (This operation requires a linear scan of the list from the beginning.) It can then access the current node of the iterator and make it bypass the node containing the item it wants to delete.

In this lab, you will be directly traversing nodes in the linked list to bypass any nodes that contain an element to be deleted.

Exercises

Exercise 1

/**
 * Remove all occurences of the specified item.
 *
 * @param x the item to remove
 */ 
public void removeAll( AnyType x )
{

}

Exercise 2

1. You will use a while loop to iterate through the nodes, searching for those with an element equal to x. Thus, you will need to add a variable declaration for the "current" node you are visiting. Add this declaration to the removeAll method.
2. What should the variable be initialized to? (Hint: Consider the case when the first item in the list is to be removed.) Add the appropriate initialization to your implementation.

Exercise 3

1. the current node
2. the element in current node
3. the current node's reference to the next node

1. What should happen to each of these things (in the body of the while loop) when the element in the next node is NOT the one to be removed? Write down your answers.
2. What should happen to each of these three things when the element in the next node IS the one to be removed? Write down your answers.
3. What should be the termination condition for your while loop? Add the while (CONDITION) {} skeleton with your condition to your implementation.
4. Based on your replies to (a) and (b) above, add the full body of the while loop (with a conditional and the appropriate actions for each outcome) to complete the routine.
5. Build the code to be sure it still compiles correctly. (You can use the shortcut C-c C-v C-b.

Exercise 4

Write a small driver program to test your implementation of removeAll. Do NOT add your program to the book code hierarchy. Instead, place it with your other files for labs you've done as part of the course.

Be sure to test cases where the object to be found is in the beginning, middle, and end of the list, as well as appears multiple times.

For Those with Extra Time

/**
 * Find the intersection of two sorted lists, assuming they are both 
 * in sorted order.
 *
 * @param listA Ordered List of Comparables
 * @param listB Ordered List of Comparables
 * @return A new ordered list containing the intersection of listA and listB
 */
public <AnyType extends <? super Comparable> static LinkedList<AnyType>
  intersect( LinkedList<AnyType> listA, LinkedList<AnyType> listB );

Exercise 5

1. Create a class called ListUtil and add the method declaration above to it.
2. Add a declaration and initialization for a new LinkedList that will be returned as the intersection in the body of the method.
3. Add declarations and initializations for iterA and iterB, iterators for listA and listB, respectively.
4. Add declarations for variables a and b, which will be elements from iterA and iterB, respectively.

Exercise 6

1. What should happen to each of the following when a.compareTo(b)==0?
   • the intersection list
   • iterA
   • iterB
2. What should happen to each of the following when a.compareTo(b)<0?
   • the intersection list
   • iterA
   • iterB
3. What should happen to each of the following when a.compareTo(b)>0?
   • the intersection list
   • iterA
   • iterB
4. The above tests should happen within a while loop. What should be the termination condition for that loop?
5. What should happen to the above elements if iterA.hasNext() is true? If iterB.hasNext() is true?

Exercise 7

1. Based on your answers to the questions in the previous exercise, complete the implementation of intersect. You may use either java.util.LinkedList or the weiss implementation.
2. Add a main method to test your code.