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

When you done with this lab, you must be cleared by the TA to receive credit.
• 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 1