You must use RECURSION to solve the problems. Your code may not contain any loops. You may not modify the method headers given to you in any way nor may you change the name of the class or the package.

package hw8; import java.util.NoSuchElementException; public class MyList { private class MyListNode { public Item item; public MyListNode next; public MyListNode(Item i, MyListNode n) { item = i; next = n; } } private MyListNode first; /** * Creates an empty list. */ public MyList() { first = null; } /** * Inserts an item at the front of the list * * @param item the item to be inserted */ public void insertAtFront(Item item) { MyListNode node = new MyListNode(item, first); first = node; } /** * Returns the number of items equal to {@code target} in the list * * @param target the data item to count * @return the number of times {@code target} appears in the list */ public int count(Item target) { return countH(first, target); } private int countH(MyListNode first, Item target) { // TODO return -1; } /** * Returns the data in position {@code index} in the list. * Note that like arrays the first data item is in position 0. * @param index the index of the item to get from the list * @throws NoSuchElementException if the list doesn't have a * position {@code index} * @return the data in position {@code index} in the list. */ public Item get(int index) { if (index < 0) throw new NoSuchElementException(); return getH(first, index); } /* Assumes index is not negative */ private Item getH(MyListNode first, int index) { // TODO return null; } /** * Constructs a separate copy of a list. Changes to the copy do not affect the original. * @return the first node of the copy */ public MyList copy() { MyList answer = new MyList(); answer.first = copyH(first); return answer; } /* returns the first node of a copy of the list whose first node is the argument first */ private MyListNode copyH(MyListNode first) { // TODO return null; }

/** * Constructs a {@code String} representation of the list. The {@code String} * is a comma separated listing of the {@code String} representations of the items * in the same order they appear in the list. There are no spaces between items. * @return a {@code String} representation of the list. */ public String convertToString() { if (first == null) return ""; return convertToStringH(first); } /* Assumes first is not null */ public String convertToStringH(MyListNode first) { // Hint: for this function, make the base case a list of size 1 // instead of using the empty list as the base case. // TODO return null; } /** * Deletes the first occurrence of {@code target} from the list if it is present. * Does nothing if {@code target} is not present. * * @param target the item to be deleted */ public void delete(Item target) { first = deleteH(first, target); } /* returns the first node of the modified list */ public MyListNode deleteH(MyListNode first, Item target) { // TODO return null; } } // ===== JUNIT TEST =====

package hw8; import java.util.NoSuchElementException; import static org.junit.Assert.*; import org.junit.Rule; import org.junit.Test; import org.junit.rules.Timeout;

public class HW6Test { @Rule public Timeout globalTimeout = Timeout.seconds(1); private static MyList makeIntList(int[] a) { MyList result = new MyList(); for(int i = a.length-1; i >= 0; i--) { result.insertAtFront(a[i]); } return result; } private static MyList makeStringList(String[] a) { MyList result = new MyList(); for(int i = a.length-1; i >= 0; i--) { result.insertAtFront(a[i]); } return result; } @Test public void test05GetOutOfBounds() { String[] a1 = {"45", "9", "18", "3", "5", "9", "88", "5", "3", "9", "2"}; String[] a2 = {"1", "3", "5", "2", "4"}; MyList l1 = new MyList(); try { l1.get(0); fail("Failed to generate exception"); } catch (NoSuchElementException e) {} l1 = makeStringList(a1); MyList l2 = makeStringList(a2); try { l1.get(-2); fail("Failed to generate exception"); } catch (NoSuchElementException e) {} try { l1.get(11); fail("Failed to generate exception"); } catch (NoSuchElementException e) {} try { l2.get(11); fail("Failed to generate exception"); } catch (NoSuchElementException e) {} try { l2.get(5); fail("Failed to generate exception"); } catch (NoSuchElementException e) {} try { l2.get(-1); fail("Failed to generate exception"); } catch (NoSuchElementException e) {} } @Test public void test05DeleteBasic() { MyList list = new MyList(); list.insertAtFront("7"); list.insertAtFront("2"); list.delete("7"); assertEquals("2", list.get(0)); assertEquals(0, list.count("7")); }

@Test public void test05DeleteAdvanced() { int[] a = {45, 9, 45, 3, 45}; MyList l1 = makeIntList(a); MyList l2 = makeIntList(a); l1.delete(45); assertEquals(9, l1.get(0).intValue()); assertEquals(45, l2.get(0).intValue()); l1.delete(45); assertEquals(9, l1.get(0).intValue()); assertEquals(3, l1.get(1).intValue()); assertEquals(45, l1.get(2).intValue()); assertEquals(9, l2.get(1).intValue()); assertEquals(3, l2.get(3).intValue()); l1.delete(45); assertEquals(9, l1.get(0).intValue()); assertEquals(3, l1.get(1).intValue()); assertEquals(45, l2.get(0).intValue()); assertEquals(9, l2.get(1).intValue()); assertEquals(45, l2.get(2).intValue()); assertEquals(3, l2.get(3).intValue()); assertEquals(45, l2.get(4).intValue()); }

}