In this assignment, we will be implementing three methods for a linked list - contains, count, and remove. See the JavaDoc comments in the file below for a description on how these methods should behave.

You should follow these steps in completing the assignment:

1) 40 points. Write JUnit 4 tests for these three methods (and these three methods only). Be sure that you consider all corner cases. You grade on this portion will be based on how well your tests find errors in your classmates submissions. If you have never written JUnit tests, the following tutorial will be helpful in getting started: https://www.codejava.net/testing/junit-tutorial-for-beginner-with-eclipseLinks to an external site.

2) 40 points. Complete the code as indicated by the TODO comments in the static recursive helper functions (and the end of the remove method).

3) 20 points. Provide an inductive argument that each one of the recursive helper functions is correct. Each argument should include the following:

a) a predicate that indicates what you wish to assert is true about the helper function. The predicate should reference n, the size of the linked list.

b) the base case: an argument that the predicate is true for the base case, i.e. when n = 0 (or maybe n=0 or n=1)

c) the inductive hypothesis: a statement about what you are assuming for values of n, 0 <= n < k.

d) the inductive step: an argument that uses the assumption in step c to argue that the predicate is true in the case where n = k.

Submit your LinkedListTest.java JUnit test file, your LinkedList.java files, and a pdf containing your inductive argument.

List.java Interface

public interface List { int length(); boolean isEmpty(); void prepend(E x); void append(E x); E getFirst(); E getLast(); void removeFirst(); void removeLast(); } 

LinkedList.java Class

import java.util.NoSuchElementException; class LinkedList implements List { private Node first, last; private int length; /** * Create an empty list */ public LinkedList() { //create an empty list - NOT NEEDED!!! first = null; last = null; length = 0; } /** * @return the number of elements stored in the list */ @Override public int length() { return length; } /** * @return true iff the list is empty */ @Override public boolean isEmpty() { return length == 0; } /** * Add an element to the front of the list * @param x the element to add */ @Override public void prepend(E x) { Node node = new Node<>(x); node.next = first; length++; if (length == 1) { last = node; } first = node; } /** * Add an element to the end of the list * @param x the element to add */ @Override public void append(E x) { Node node = new Node<>(x); length++; if (length == 1) { first = node; } else { last.next = node; } last = node; } /** * @returns the first element in the list, or null if the list is empty */ @Override public E getFirst() { if (first == null) { return null; } return first.data; } /** * @returns the last element in the list, or null if the list is empty */ @Override public E getLast() { if (last == null) { return null; } return last.data; } /** * Remove the first element in the list * @throws NoSuchElementException if the list is empty */ @Override public void removeFirst() { if (first == null) { throw new NoSuchElementException(); } first = first.next; length--; if (length == 0) last = null; } /** * Remove the last element in the list * @throws NoSuchElementException if the list is empty */ @Override public void removeLast() { if (last == null) { throw new NoSuchElementException(); } length--; if (length == 0) { first = null; last = null; } else { Node p = first; while (p.next != last) { p = p.next; } p.next = null; last = p; } } /************************************************************************ * Linked List methods for you to complete *************************************************************************/ /** * Search the list * @param x the search value * @return true iff the list contains the element x */ public boolean contains(E x) { return containsHelper(first, x); } static  boolean containsHelper(Node n, T x) { // TODO: Implement this method using recursion. // Note you should only process one node per recursive call return false; } /** * Count the occurences of a value in the list * @param x the search value * @return the number of times x appears in the list */ public int count(E x) { return countHelper(first, x); } static  int countHelper(Node n, T x) { // TODO: Implement this method using recursion. // Note you should only process one node per recursive call return 0; } /** * A class to help you with the remove method */ static class ReturnValue { Node first; Node last; int length; } /** * Remove all elements in the list that matches x * @param x the search value * @return the number of values that were removed */ public int remove(E x) { ReturnValue retVal = removeHelper(first, x); // TODO: Complete this method return 0; } /** * Remove all instances of x from the list starting at node n * @param n the first node in the list * @param x the target value * @return the first node, last node, and number of nodes in the list after instances * of x have been removed */ static  ReturnValue removeHelper(Node n, T x) { // TODO: Implement this method using recursion. // Note you should only process the current node in this recursive call // You may not create new nodes. // You should only create one Return Value object. It should only be created in the // base case. return null; } private static class Node { public T data; public Node next; public Node(T value) { data = value; } } }