interface Node { public int size(); //returns size of list (# values) starting with this Node public boolean contains(T val); //returns whether list starting with this Node contains val public T get(int index); //return value at given index (0 is list starting at this Node) //throws IndexOutOfBoundsException if index is invalid public int indexOf(T val); public Node add(T val); //returns new list with value at the end }

class EmptyNode implements Node { public int size() { return 0; } public boolean contains(T val) { return false; } public T get(int index) { throw new IndexOutOfBoundsException(); } public int indexOf(T val) { return -1; } public Node add(T val) { return new NonEmptyNode(val, this); } }

class NonEmptyNode implements Node { T value; Node next;

public NonEmptyNode(T value, Node next) { this.value = value; this.next = next; } public int size() { return 1 + next.size(); } public boolean contains(T val) { if(value.equals(val)) //checking if this node has value return true; return next.contains(val); //checking rest of list //return value.equals(val) || next.contains(val); } public T get(int index) { if(index == 0) return value; return next.get(index-1); } public int indexOf(T val) { if(value.equals(val)) return 0; int ret = next.indexOf(val); if(ret == -1) return -1; return ret + 1; } public Node add(T val) { next = next.add(val); return this; } }

public class RecursiveList {

private Node head;

public RecursiveList() { head = new EmptyNode(); }

public void addFront(T value) { head = new NonEmptyNode(value, head); }

public int size() { return head.size(); } public boolean contains(T val) { return head.contains(val); } public T get(int index) { return head.get(index); } public int indexOf(T val) { return head.indexOf(val); } public void add(T val) { head = head.add(val); } }

You may build on the code we've written in class (available as hw5given.zip) or the code you wrote for lab. 1. (18 points) Implement each of the methods below for our RecursiveList class. These should actu- ally use recursion (no loops). You will not be graded on test cases, but create some to ensure that your methods work. (a) changeTo, which takes two values and replaces all occurrences of the first value with the second value. If the first value doesn't appear in the list, the list is unchanged. (b) A version of add that takes an index and a value, adding the value to the list so that it has the given index. (Giving 0 means the value becomes the first element, the list length means it becomes the last element, etc.) If the index is invalid, the method should throw an IndexOutOf BoundsException. (c) A version of remove that takes an index and removes the value at that index. If the index is invalid, the method should throw an IndexOutOfBoundsException