CSE 131 Module 8: List Structures


Update your svn repository as usual to get the lab8 package.

IMPORTANT: Do not modify the provided toString method in the ListItem class, since our automated tests depend on the specific formatting it produces.

Project: Linked List Manipulation

In Module 6, you used the LinkedList class as an abstraction to represent the coefficients of polynomials. However, the internal representation was encapsulated within each LinkedList object and you operated on it only in terms of the methods in the List interface. In this lab, you will be working with directly with "raw" list structure, using references to traverse lists and manipulating references to change the structure of lists.
  1. In the file ListItem.java, write methods for the ListItem class that satisfisfy the following specifications. In each case, be sure to use recursion or iteration as specified. Where not indicated, you may choose either approach.
    • Use the JUnit test cases provided to guide the development of your methods, and continually test-as-you-go.
    • Hints: Draw lots of pictures before writing any code. Try small examples and hand simulate how your algorithm will work. Use small lists for testing in JUnit so you can draw the corresponding pictures. Then, if things don't work as expected, use the debugger to examine the list structure itself in memory. To do this, set a breakpoint at a line in the test case where you want the debugger to pause. Then, choose "debug as" instead of "run as" in Eclipse. Use the "step over" and "step into" methods to single step through the code, and examine the list structure in the "variables" view by opening up the "next" references to see what they refer to.
    1. A recursive method duplicate that takes no parameters and returns a new ListItem that begins a list containing the same numbers (but not the same ListItem objects) as the original list. (We did this one in class, but try to do it without looking at your notes.)

    2. A recursive method length that takes no parameters and returns the number of elements in the list. For example, the list (3 5 9 3 2 4) would have length 6.

    3. An iterative method stretch that takes a positive number n as a parameter and returns a new ListItem beginning a list in which each of the numbers in the original list is repeated n times. For example, if the original list is ( 6 7 6 9 ) and the parameter value is 2, then the new list returned is ( 6 6 7 7 6 6 9 9 ).

    4. A method find that takes an integer target and returns the first ListItem in the list that contains the given number. If the target does not occur in the list, then null is returned.

    5. A method max that returns the largest number in the list. Hint: You know that the maximum value must be at least as large as the number in the first ListItem.

    6. In the file ListItem.java, write a static method that satisfies the following specification. Remember that static methods are called directly on the ListItem class itself, rather than on ListItem objects. To call static methods of the ListItem class from your JUnit test methods, you can specify the class name each time, as in ListItem.evenElements(ls). Alternatively, you can save characters and just write evenElements(ls) if you import the static methods from the ListItem class by adding the line
      import static lab8.ListItem.*;
      near the top of your file, after the package declaration.

      A recursive procedure evenElements

      PARAMETERS:   a ListItem reference, ls
      RETURN VALUE: a ListItem at the beginning of a list structure
                    containing copies of the even numbers in given list.
                       for example, given input list ( 3 2 6 9 ), the
                       return value would be the list ( 2 6 )

    Submitting your work (read carefully)

    Last modified 22:14:03 CST 11 November 2009 by Ron K. Cytron