Laboratory: Linked Lists
CSC 207 Algorithms and Object Oriented Design Spring 2009

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

Recall that the class weiss.nonstandard.LinkedList class has only one member variable: 
private ListNode<AnyType> header;
The class weiss.nonstandard.ListNode has just two member variables: 
public AnyType element;
public ListNode<AnyType> next;
This setup is typical for a singly linked list.

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

Add the following method signature to weiss.nonstandard.LinkedList.java 
/**
 * Remove all occurence of an item.
 * @param x the item to remove
 */ 
public void removeAll( AnyType x )
{

}

Exercise 2

  1. You will need to iterate through the nodes, searching for those with an element equal to x. Use a while loop for this purpose. Thus, you will need to declare the "current" node you are visiting. Add a variable declaration for such a node to your implementation.
  2. What should the variable be initialized to? Add this to your implementation.

Exercise 3

There are two conditions you'll need to worry about in the body of your loop. (Keep in mind that since we have a singly-linked list, there is no way to "go back" to a previous node once you've lost the reference to it.) The salient things you'll need to worry about are the only things you have on hand:
  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?
  2. What should happen to each of these three things when the element in the next node IS the one to be removed?
  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, 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. Be sure to test cases where the object to be found is in the beginning, middle, and end of the list.

For Those with Extra Time

Now that you've done a little reference manipulation, we can return to some more "logical" processing of lists. Assume two lists of Comparable items are in sorted order. We can easily find the intersection of these two collections. Consider the following method declaration: 

/**
 * Find the intersection of two sorted lists.
 *
 * @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. Add a declaration and initialization for a new LinkedList that will be returned as the intersection.
  2. Add declarations and initializations for iterA and iterB, iterators for listA and listB, respectively.
  3. Add declarations for variables a and b, which will be elements from iterA and iterB, respectively.

Exercise 6

To find the intersection, you will need to iterate over all elements in both lists. Assuming a and b are the current elements from each list's iterator, write down your answers to each of the following questions.
  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 implement intersect in its own class file. You may use either tjava.util.LinkedList or the weiss implementation.
  2. Add a main method to test your code.
Created: Jerod Weinman, 18 March 2009