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

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.


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.


Exercise 1

Add the following method signature to
 * 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

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. the current node
  2. the element in current node
  3. the current node's reference to the next node
With these in mind, answer the following questions:
  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

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, 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

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, 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.
Created: Jerod Weinman, 18 March 2009
Modified: Jerod Weinman, 14 April 2011
Copyright © 2009-2011 Jerod Weinman.
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License .