## 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.

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 )
```

• You must commit all of your work to your repository. It's best to do this from the top-most level of your repository, which bears your name and student ID.
• You must demo the commited work to a TA. Make sure the TA knows that your demo is for credit at this point.
• Follow the directions below to have your demo for this work recorded.