CSE 131 Module 9: Lists

Lab

Update your svn repository as usual to get the lab9 package in the labs source folder.

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 8, 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 in ListItemTest 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.

    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.

      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 )

    Make sure your code passes both unit tests in your repo before asking to demo.

    Submitting your work (read carefully)


    Last modified 11:27:54 CST 30 November 2012
    When you done with this lab, you must be cleared by the TA to receive credit.
    • Commit all your work to your repository
    • Fill in the form below with the relevant information
    • Have a TA check your work
    • The TA should check your work and then fill in his or her name
    • Click OK while the TA watches

    If you worked in a team using a group– repository:
    • Your work must be committed in that repository for this demo.
    • Each team member must complete this form and have the TA authenticate.
      For example, if there are two of you, then the form must be submitted twice, so that each person's last name and 6 digit ID is captured with the repository name.
    • The repository name must be included on each of the submissions.
    group– ←Enter the name of your group repository here
    Last name 6-digit ID
    1
    TA: Password: