CS 136 Tutorials - Spring 2007

Tutorial 10: List Processing, Generics, and Iteration (July 6)

Today's tutorial covers list processing in Java using the GenList class. We will see the use of generics, and will write methods in both the recursive and iterative style. The topics for today's tutorial come from lecture modules 9 and 10 (see handouts).

You won't be able to do much for this tutorial without the skeleton code. It's available in a zip file or a gzipped tar.

  1. Recursive List Processing
    • Reading Java code and comments
    • Look at the code for the FrequencyPair class and the FrequencyListTest class first. You should be able to understand how the FrequencyPair class is used and what its function is, and you should have a rough idea of what the FrequencyList class does.

      Note that we are looking at the tests before we even see the skeleton code for the class! There is actually a theory which says this is correct - to write tests for a class before we write the code. This is called "test-driven development".

    • Implementing the methods
    • Now look at the skeleton code for the FrequencyList class. The documentation in this class should be sufficient to completely describe the behavior of each method. Use recursion to implement all the methods in the class except for mostFrequent(int k). Note that you will have to write helper methods for most of these.

      Use the FrequencyListTest class to test your implementation.

  2. Iterative List Processing
  3. Now rewrite all the methods you just implemented using iteration instead of recursion for the list processing. You shouldn't need any helper methods now. Again, test with FrequencyListTest.

  4. One more method...
  5. Now go back and implement the method we skipped, mostFrequent(int k) First write the method using recursion, then using iteration. Make use of the provided helper method, insert. For a final challenge, rewrite insert to use iteration instead of recursion.


Last modified on Friday, 19 August 2011, at 18:05 hours.