---
tags: resources, spr22
---

# A Worked Example of writing a `MutableList` method

This handout works through the problem-solving steps involved in writing a `MutableList` method of a style like you might get on a homework. Hopefully, seeing this will help those of you who are still trying to finish `HW2`.

**Task:** Write a method `contains` in the `MutableList` class that takes an item and returns a boolean indicating whether the given item is in the list.

### How to Approach Producing the Code

1. Draw a picture of a concrete MutableList, to help you understand the objects involved, and perhaps to help plan out modifications.

3. Work out a couple of concrete examples (that will become tests) of how `contains` should behave: this makes sure that you understand what the inputs and outputs will be

    - Create a TestList containing ["Hello", "Brown", "bear"]
    - TestList.contains("Hello") should be true
    - TestList.contains("hello") should be false 

3. Set up the method in the `MutableList` class.

class MutableList {
   Node start;
   Node end;
   /**
     * Determine whether the list contains a specific item
     * @param searchFor - the item to search for
     * @return - whether the item is in the list
     */
   public boolean contains(String searchFor) {
     ...
   }
}

4. Now start filling in the method. Ask yourself whether the fields of `MutableList` have sufficient information to complete the computation. If not, consider whether you can `delegate` part of the computation to another object. In this case, `MutableList` doesn't directly know what items are in the list, but the `start` Node might know. The `MutableList` method will therefore delegate to `this.start`

class MutableList {
   Node start;
   Node end;
   /**
     * Determine whether the list contains a specific item
     * @param searchFor - the item to search for
     * @return - whether the item is in the list
     */
   public boolean contains(String searchFor) {
     // the method on the Node class doesn't have to use the same name.
     // you'll decide based on the computation that you need the Node to do
     return this.start.contains(searchFor);
   }
}

Setting up the delegation means that you have to write the needed method in the class that you delegated to:

class Node {
  String item;
  
  public boolean contains(String searchFor) {
     ...
  }
}

What should the `contains` method in the`Node` class do? Take the same approach as we did in the `MutableList` class: ask whether a specific `Node` object has the info needed to complete the computation. Each `Node` object has a single item value. If the item is the one being searched for, the the current `Node` object can return the value. But if it isn't, then the current `Node` has to delegate to the next node in the list. This gives the following code:

class Node {
  String item;
  Node next;
  
  public boolean contains(String searchFor) {
     if (this.item.equals(searchFor)) {
        return true;
     } else {
        return this.next.contains(searchFor);
     }
  }
}

:::success
This view of objects **delegating** work to other objects gets at many of the points we've tried to make so far about good object-oriented design so far (though this way of explaining it is new compared to lecture). If you are stuck getting started on code, follow what we did here:
- write a method with the name and input types you've been asked to implement, then
- figure out what work of that method should get delegated to the objects available through fields and input parameters. Call off to those other objects to do their part, then
- put the pieces together in the original method body.
:::

### Testing

Now turn the initial examples into JUnit tests and run the `main` method in `TestRunner`.

All looks good -- our tests passed! We upload to Gradescope, but the autograder shows that we're not passing all of the tests. That means there are cases we haven't thought about. We step back, and reconsider the code.

#### What might our tests have missed?

As a general rule, we should think about the variations that could happen in our data and make sure we are covering them. For example, we tested a string in the list, a string from the list with different capitalization, and a string not in the list. These are some good variations, but we should consider some other situations:
- (Possible Method Outputs) What if the string we're looking for isn't in the list?
- (String Relationships) What if the given string is a substring or superstring of one in the list? What if the string is alphabetically before or after all others in the list?
- (String Positions) What if the string we are looking for is in the middle of the list? At the end of the list?
- (Precision of "contains") What if the string is in the list more than once?
- (List Structure) What if the list is empty

:::success
**Testing:** Step back and notice what kinds of things we considered here: possible outputs (based on the output type), possible shapes of our data structures, possible positions of items in our data structures, possible variations on the kinds of data the method might confront (and how they might relate the the values of other basic data). These aren't specific to `contains`: these are part of the general strategy of designing a good set of tests!
:::

### Back to the code

If you were to turn these newly-identified cases into tests and run them, you'd get an error on a test for an element that isn't in the list. Specifically, you'd get a `NullPointerException` when checking an element that isn't in the list.

`NullPointerException` means that you tried to call a method or access a field through the name of an object that is currently associated with `null`, not an actual `Object`. Here, the problem arises with `this.next`: if the item isn't in the list, we will eventually "run out of list", so `this.next` will be `null`. Our code in the `Node` class has to check for this situation:

class Node {
  String item;
  Node next;
  
  public boolean contains(String searchFor) {
     if (this.item.equals(searchFor)) {
        return true;
     } else if (this.next == null) {
        return false;
     } else {
        return this.next.contains(searchFor);
     }
  }
}

Making this fix and running the expanded set of tests should now show all of the tests are working.

## Discussion

**Developing Recursive Functions:** In class, we approached writing methods like `contains` a little differently: we expected that you understood that you had to traverse the list, and thus needed to use recursion. That left you with the challenge of figuring out how to write recursive functions over objects and where to put different methods to make that happen. These notes are trying a different approach.

:::success
**Recursion arises from Delegation:** In these notes, we're arriving at a recursive function by thinking about how objects delegate computation to one another, rather than trying to do computations themselves with data that live in other objects. If starting from a decision to implement recursively hasn't worked for you, try approaching the problems with the "delegation" narrative and see whether that helps.

Note that the delegation narrative is also more general: we will find ourselves using this even in problems that aren't recursive, but that do require computation from other objects.
:::

**Testing:** We've tried here to give you some concrete guidelines to what to think about when designing tests. If you think systematically about the possible variations in input shape, data position, and relationships among data, you should do fine in the testing component of the course.

As for detecting chaffs, we generate the chaffs by violating different testing guidelines: substituting `>` for `>=` (and vice versa), writing versions that made assumptions on capitalization, on order, on where in a list data might be (or not). You don't need a separate set of guidelines for finding chaffs. You just have to be systematic in identifying ways that data or implementations might go wrong relative to what a problem statement expects.