Hi, I need help with Visual Studio Coding.

Development Notes 1. Figure out the order of ToDos Your main task is to implement RecursiveList.java. You'll find a bunch of TODOs in the starter code. Spend some time tracing what should happen when a new RecursiveList is created in LinkedListMain and the insertLast method in RecursiveList.java.is called. You'll find it helpful to read the comments in ListInterface.java. You'll see that all the methods in the interface are implemented in RecursiveList.java (with @Override). 2. Use Recursion In your implementation, you must use recursion and you may not use explicit iteration (i.e. for, while, or do while loops) of any kind. You will not receive any points if you submit an implementation using explicit iteration. Hints: Recursion is all about reducing some problems slightly to make it easier to solve. For some methods, to implement them using recursion, you will find it necessary to create private, "helper" methods that are recursive, and then have your public methods call these helper methods to jump start the recursive call. You have to decide what arguments these helper methods need in order to implement them recursively. Review ZyBooks chapters 12.19 and 12.20 for an overview of recursion. You'll also find extra resources in Moodle for understanding how recursion works. In particular, see the Echo 360 links to 2 videos: "Optional: Recursion Intro" and "Optional: recursion on Lists". (Note: chapter names and numbers in the videos do not match chapters in the current zyBooks). 3. Use Helper Methods Let's look at a specific example of a helper method for this project: take a look at the indexof method this public method is written in such a way that does not lend itself to recursion on a linked list node. So you should create a private helper method to use internally. Perhaps something like: private int indexOfHelper (T elem, int index, Node node) We can then simply ask, does the current node contain the element you are looking for? If it does, we can return the current index. Otherwise, we recurse on the next node in the list, at the next index, with the same element to search for. Think about what the base cases are. Another suggested helper method would be: private final Node findNode (int distance, Node curr) This method finds the node that is an integer) distance nodes after curr. That is, if distance is 0, then curr is returned. Otherwise, recur down the list. 4. Stay within Big-O runtime bounds Be sure that your implementation complies with the required Big-O runtime bounds in the comments of each method as described in the ListInterface interface. Your code will not pass all of the autograder tests if your methods are not within these bounds. For e.g. the size () method must run in O(1) time. 5. Implement the Iterator method The ListInterface extends Iterable (see API documentation). You will need to implement the iterator () method that returns an Iterator. Your implementation of the iterator () method can simply create a new Iterator each time it is called. 6. Throw Exceptions The use of Exceptions is an important part of programming. They are the best way to signal to the caller that a method encountered an unexpected, or abnormal condition. Review zyBooks chapters 12.17 and 12.18 for Exception Basics and Exceptions with Methods. You will see several kinds of Exceptions in this code. One example is the remove method (called in the main method with the sample input data). It throws several types of Exceptions including an ItemNotFoundException. This Exception class is part of the project code in the app package. 22 900 143 8 900 143 8 900 143 900 Exception in thread "main" app. ItemNotFoundException: Item was not found in the list. at app. RecursiveList.remove(RecursiveList.java:228) at app.LinkedListMain.main(LinkedListMain.java:19) Tests We have provided you with some public tests and some private tests in Gradescope. You will need to come up with some of your own. Try to think of all of the edge cases that could occur, and write tests to check for each of them. You will not be graded on your tests, but writing them and passing them is the only way that you can be reasonably sure that your code works. Remember: Do not modify any existing instance variables, method signatures or any of the starter code provided. Do not import any code libraries. 1 src > app > Item NotFoundException.java > ... package app; 2 /** * A {@link ItemNotFoundException} is thrown at runtime when a data item is searched for but not found. */ 6 public class ItemNotFoundException extends RuntimeException { private static final long serialversionUID = 11; 4 Nm in N 000 public ItemNotFoundException() { super(); } 10 11 12 13 14 public ItemNotFoundException(String message) { super(message); } 15 16 } 17 src > app LinkedList Main.java > ... 1 package app; Nm in import java.util.Iterator; 4 6 7 8 9 10 11 12 public class LinkedListMain { Run Debug public static void main(String[] args) { ListInterface list = new Recursivelist(); list.insertLast(22); list.insertLast(900); list.insertLast(143); list.insertLast(); System.out.println(printList(list)); list.removeFirst(); System.out.println(printList(list)); list.removeLast(); System.out.println(printList(list)); list.removeAt(1); System.out.println(printList(list)); list.remove(100); // should throw an ItemNotFoundException } 13 14 15 16 17 18 19 20 21 22 23 24 25 public static String printList(ListInterface list) { StringBuilder sb = new StringBuilder(); Iterator listIter = list.iterator(); while (listIter.hasNext()) sb.append(listIter.next().append(" "); return sb.toString(); } 26 27 28 29 } 30 31 src > app LinkedNodelterator.java > R$ LinkedNodelterator 1 package app: 2 3 import java.util.Iterator; 4 5 class LinkedNodeIterator implements Iterator private Node next; 6 7 8 9 public LinkedNodeIterator (Node first) { this.next = first; } 10 11 12 13 public boolean hasNext() { return next != null; } 14 15 16 17 18 public T next() { I result next.getData(); next = next.getNext(); return result; } 19 20 21 22 23 24 25 public void remove() { throw new UnsupportedoperationException(); } 1 src > app > ListInterface.java > ... package app; 1 N min import java.util.Iterator; * A {@link ListInterface} is a container that supports insertion, removal, and searching 3 7 3 8 9 10 * @param : generic type 11 public interface ListInterface extends Iterable { 12 13 14 15 Returns the number of elements in this {@link ListInterface). This method runs in 0(1) time. */ public int size(); 16 17 18 19 20 21 Adds an element to the front of this {@link ListInterface}. This method runs * in 0(1) time. For convenience, this method returns the {@link ListInterface} that was modified. @param elem the element to add - A DI N S B 8 8 8 8 H B T N @throws NullPointerException if {@code elem} is {@code null} @throws Exception if */ public void insertFirst(i elem); Adds an element to the end of this {@link ListInterface). This method runs in * 0(size) time. For convenience, this method returns the {@link ListInterface} that was modified. 36 @param elem the element to add @throws NullPointerException if {@code elem} is {@code null} 37 38 39 public void insertLast(T elem); 40 41 42 43 44 45 Adds an element at the specified index such that a subsequent call to * {@link ListInterface#get(int)} at {@code index} will return the inserted value. This method runs in 0(index) time. 46 47 48 @param index the index to add the element at @param elem the element to add @throws NullPointerException if {@code elem} is {@code null} 49 50 51 @throws IndexOutOfBoundsException if {@code index} is less than @ or greater than (@link ListInterface#size()} public void insertAt(int index, T elem); 52 53 54 55 56 57 /** Removes the first element from this {@link ListInterface) and returns it. This method runs in 0(1) time. 58 @return the removed element @throws IllegalStateException if the {@link ListInterface} is empty. 59 60 61 public I removeFirst(); 62 63 64 65 /**

Removes the last element from this {@link ListInterface) and returns it. This * method runs in O(size) time.

66 67 68 69 @return the removed element @throws IllegalStateException if the {@link ListInterface} is empty. 70 71 72 73 public I removeLast(); 74 75 76 /** Removes the ith element in this {@link ListInterface and returns it. This * method runs in 0(i) time. 77 78 79 80 @param i the index of the element to remove @return The removed element @throws IndexOutOfBoundsException if {@code i} is less than or {@code i} is greater than or equal to {@link ListInterface#size() } 81 82 83 84 85 public I removeAt(int i); 86 87 88 89 90 Returns the first element in this {@link ListInterface). This method runs in 0(1) time. 91 @return the first element in this {@link ListInterface). @throws IllegalStateException if the {@link ListInterface} is empty. */ public I getFirst(); 92 93 94 95 96 * Returns the last element in this {@link ListInterface}. This method runs in o(size) time. 97 98 99 100 101 @return the last element in this {@link ListInterface}. @throws IllegalStateException if the {@link ListInterface) is empty. */ public getLast(); 102 103 104 105 * Returns the ith element in this {@link ListInterface). This method runs in 0(i) time. 106 107 108 109 110 @param i the index to lookup @return the ith element in this {@link ListInterface}. @throws IndexOutOfBoundsException if {@code i} is less than or {@code i} is greater than or equal to {@link ListInterface#size()} 111 112 113 114 public I get(int i); 115 116 117 118 * Removes {@code elem} from this {@link ListInterface} if it exists. If multiple instances of {@code elem} exist in this {@link ListInterface} the one associated with the smallest index is removed. This method runs in 0(size) time. 119 120 121 122 123 @param elem the element to remove @throws NullPointerException if {@code elem} is {@code null} @throws ItemNotFoundException if {@code elem} is not in the list. */ public void remove(T elem); 124 125 126 127 128 129 130 131 132 133 /** * Returns the smallest index which contains {@code elem}. If there is no * instance of {@code elem} in this {@link ListInterface} then -1 is returned. This method runs in O(size) time. 134 @param elem the element to search for @return the smallest index which contains {@code elem} or -1 if {@code elem} is not in this {@link ListInterface} @throws NullPointerException if {@code elem} is {@code null} 135 136 137 138 public int indexOf(T elem); 139 140 141 142 * Returns {@code true} if this {@link ListInterface} contains no elements and {@code false} otherwise. This method runs in 0(1) time. 143 144 145 146 @return {@code true} if this {@link ListInterface) contains no elements and {@code false} otherwise. */ public boolean isEmpty(); 147 148 149 150 * Returns an Iterator object that will traverse this list. 151 152 153 @return an Iterator object. public Iterator iterator(); 154 155 156 157 } src > app > Node.java >. package app; 1 2 3 4. public class Node { private I data; private Node next; 5 6 7 8 9 10 public Node(T data, Node next) { this.data data; this.next = next; } 11 12 13 public I getData() { return data; } 14 15 16 17 18 19 public Node getNext() { return next; } 20 21 22 public void setData(T data) { this.data = data; } 23 24 25 public void setNext(Node next) { this.next = next; } 26 27 } 28 src > app > RecursiveList.java > RecursiveList > iterator 1 package app; 2 import java.util.Iterator; 4 5 public class RecursiveList implements ListInterface { 3 6 7 8 9 10 private int size; private Node head = null; 11 12 13 public RecursiveList() { this.head = null; this.size = 0; } 14 15 16 17 public Recursivelist(Node first) { this.head = first; this.size = 1; } 18 19 20 21 22 23 @Override public int size() { return size; } 24 25 26 27 @Override public void insertFirst(1 elem) { //TODO: Implement this method. 28 29 } 30 31 32 @Override public void insertLast(elem) { //TODO: Implement this method. 33 } 34 35 36 37 38 39 40 @Override public void insertAt(int index, 1 elem) { //TODO: Implement this method. 41 } 42 43 44 45 46 @Override public I removeFirst() { I removed Item null; //TODO: Implement this method. 47 48 return removedItem; 49 } 50 51 52 @Override public I removeLast() { I removed Item = null; //TODO: Implement this method. 53 54 55 56 return removedItem; } 57 58 59 60 @Override public I removeAt(int i) { I removed Item = null; //TODO: Implement this method. 61 62 63 64 return removedItem; } 65 66 67 68 69 70 71 @Override public I getFirst() { I item = null; //TODO: Implement this method. return item; } 72 73 74 75 76 @Override public I getLast() { I item null; //TODO: Implement this method. 77 78 79 80 return item; 81 } 82 83 84 @Override public I get(int i) { T item = null; //TODO: Implement this method. 85 86 87 return item; 88 89 90 } 91 92 @Override public void remove(t elem) { //TODO: Implement this method. 93 94 95 } 96 96 97 98 @Override public int indexOf(T elem) { int index = -1; //TODO: Implement this method. 99 return index; } 100 101 102 103 104 105 106 107 108 @Override public boolean isEmpty() { boolean empty = false; //TODO: Implement this method. 109 return empty; } 110 111 112 113 114 115 116 117 118 public Iterator iterator() { Iterator iter = null; | // TODO: Implement this method: 119 return iter; ] 120 121 } 122 Development Notes 1. Figure out the order of ToDos Your main task is to implement RecursiveList.java. You'll find a bunch of TODOs in the starter code. Spend some time tracing what should happen when a new RecursiveList is created in LinkedListMain and the insertLast method in RecursiveList.java.is called. You'll find it helpful to read the comments in ListInterface.java. You'll see that all the methods in the interface are implemented in RecursiveList.java (with @Override). 2. Use Recursion In your implementation, you must use recursion and you may not use explicit iteration (i.e. for, while, or do while loops) of any kind. You will not receive any points if you submit an implementation using explicit iteration. Hints: Recursion is all about reducing some problems slightly to make it easier to solve. For some methods, to implement them using recursion, you will find it necessary to create private, "helper" methods that are recursive, and then have your public methods call these helper methods to jump start the recursive call. You have to decide what arguments these helper methods need in order to implement them recursively. Review ZyBooks chapters 12.19 and 12.20 for an overview of recursion. You'll also find extra resources in Moodle for understanding how recursion works. In particular, see the Echo 360 links to 2 videos: "Optional: Recursion Intro" and "Optional: recursion on Lists". (Note: chapter names and numbers in the videos do not match chapters in the current zyBooks). 3. Use Helper Methods Let's look at a specific example of a helper method for this project: take a look at the indexof method this public method is written in such a way that does not lend itself to recursion on a linked list node. So you should create a private helper method to use internally. Perhaps something like: private int indexOfHelper (T elem, int index, Node node) We can then simply ask, does the current node contain the element you are looking for? If it does, we can return the current index. Otherwise, we recurse on the next node in the list, at the next index, with the same element to search for. Think about what the base cases are. Another suggested helper method would be: private final Node findNode (int distance, Node curr) This method finds the node that is an integer) distance nodes after curr. That is, if distance is 0, then curr is returned. Otherwise, recur down the list. 4. Stay within Big-O runtime bounds Be sure that your implementation complies with the required Big-O runtime bounds in the comments of each method as described in the ListInterface interface. Your code will not pass all of the autograder tests if your methods are not within these bounds. For e.g. the size () method must run in O(1) time. 5. Implement the Iterator method The ListInterface extends Iterable (see API documentation). You will need to implement the iterator () method that returns an Iterator. Your implementation of the iterator () method can simply create a new Iterator each time it is called. 6. Throw Exceptions The use of Exceptions is an important part of programming. They are the best way to signal to the caller that a method encountered an unexpected, or abnormal condition. Review zyBooks chapters 12.17 and 12.18 for Exception Basics and Exceptions with Methods. You will see several kinds of Exceptions in this code. One example is the remove method (called in the main method with the sample input data). It throws several types of Exceptions including an ItemNotFoundException. This Exception class is part of the project code in the app package. 22 900 143 8 900 143 8 900 143 900 Exception in thread "main" app. ItemNotFoundException: Item was not found in the list. at app. RecursiveList.remove(RecursiveList.java:228) at app.LinkedListMain.main(LinkedListMain.java:19) Tests We have provided you with some public tests and some private tests in Gradescope. You will need to come up with some of your own. Try to think of all of the edge cases that could occur, and write tests to check for each of them. You will not be graded on your tests, but writing them and passing them is the only way that you can be reasonably sure that your code works. Remember: Do not modify any existing instance variables, method signatures or any of the starter code provided. Do not import any code libraries. 1 src > app > Item NotFoundException.java > ... package app; 2 /** * A {@link ItemNotFoundException} is thrown at runtime when a data item is searched for but not found. */ 6 public class ItemNotFoundException extends RuntimeException { private static final long serialversionUID = 11; 4 Nm in N 000 public ItemNotFoundException() { super(); } 10 11 12 13 14 public ItemNotFoundException(String message) { super(message); } 15 16 } 17 src > app LinkedList Main.java > ... 1 package app; Nm in import java.util.Iterator; 4 6 7 8 9 10 11 12 public class LinkedListMain { Run Debug public static void main(String[] args) { ListInterface list = new Recursivelist(); list.insertLast(22); list.insertLast(900); list.insertLast(143); list.insertLast(); System.out.println(printList(list)); list.removeFirst(); System.out.println(printList(list)); list.removeLast(); System.out.println(printList(list)); list.removeAt(1); System.out.println(printList(list)); list.remove(100); // should throw an ItemNotFoundException } 13 14 15 16 17 18 19 20 21 22 23 24 25 public static String printList(ListInterface list) { StringBuilder sb = new StringBuilder(); Iterator listIter = list.iterator(); while (listIter.hasNext()) sb.append(listIter.next().append(" "); return sb.toString(); } 26 27 28 29 } 30 31 src > app LinkedNodelterator.java > R$ LinkedNodelterator 1 package app: 2 3 import java.util.Iterator; 4 5 class LinkedNodeIterator implements Iterator private Node next; 6 7 8 9 public LinkedNodeIterator (Node first) { this.next = first; } 10 11 12 13 public boolean hasNext() { return next != null; } 14 15 16 17 18 public T next() { I result next.getData(); next = next.getNext(); return result; } 19 20 21 22 23 24 25 public void remove() { throw new UnsupportedoperationException(); } 1 src > app > ListInterface.java > ... package app; 1 N min import java.util.Iterator; * A {@link ListInterface} is a container that supports insertion, removal, and searching 3 7 3 8 9 10 * @param : generic type 11 public interface ListInterface extends Iterable { 12 13 14 15 Returns the number of elements in this {@link ListInterface). This method runs in 0(1) time. */ public int size(); 16 17 18 19 20 21 Adds an element to the front of this {@link ListInterface}. This method runs * in 0(1) time. For convenience, this method returns the {@link ListInterface} that was modified. @param elem the element to add - A DI N S B 8 8 8 8 H B T N @throws NullPointerException if {@code elem} is {@code null} @throws Exception if */ public void insertFirst(i elem); Adds an element to the end of this {@link ListInterface). This method runs in * 0(size) time. For convenience, this method returns the {@link ListInterface} that was modified. 36 @param elem the element to add @throws NullPointerException if {@code elem} is {@code null} 37 38 39 public void insertLast(T elem); 40 41 42 43 44 45 Adds an element at the specified index such that a subsequent call to * {@link ListInterface#get(int)} at {@code index} will return the inserted value. This method runs in 0(index) time. 46 47 48 @param index the index to add the element at @param elem the element to add @throws NullPointerException if {@code elem} is {@code null} 49 50 51 @throws IndexOutOfBoundsException if {@code index} is less than @ or greater than (@link ListInterface#size()} public void insertAt(int index, T elem); 52 53 54 55 56 57 /** Removes the first element from this {@link ListInterface) and returns it. This method runs in 0(1) time. 58 @return the removed element @throws IllegalStateException if the {@link ListInterface} is empty. 59 60 61 public I removeFirst(); 62 63 64 65 /**

Removes the last element from this {@link ListInterface) and returns it. This * method runs in O(size) time.

66 67 68 69 @return the removed element @throws IllegalStateException if the {@link ListInterface} is empty. 70 71 72 73 public I removeLast(); 74 75 76 /** Removes the ith element in this {@link ListInterface and returns it. This * method runs in 0(i) time. 77 78 79 80 @param i the index of the element to remove @return The removed element @throws IndexOutOfBoundsException if {@code i} is less than or {@code i} is greater than or equal to {@link ListInterface#size() } 81 82 83 84 85 public I removeAt(int i); 86 87 88 89 90 Returns the first element in this {@link ListInterface). This method runs in 0(1) time. 91 @return the first element in this {@link ListInterface). @throws IllegalStateException if the {@link ListInterface} is empty. */ public I getFirst(); 92 93 94 95 96 * Returns the last element in this {@link ListInterface}. This method runs in o(size) time. 97 98 99 100 101 @return the last element in this {@link ListInterface}. @throws IllegalStateException if the {@link ListInterface) is empty. */ public getLast(); 102 103 104 105 * Returns the ith element in this {@link ListInterface). This method runs in 0(i) time. 106 107 108 109 110 @param i the index to lookup @return the ith element in this {@link ListInterface}. @throws IndexOutOfBoundsException if {@code i} is less than or {@code i} is greater than or equal to {@link ListInterface#size()} 111 112 113 114 public I get(int i); 115 116 117 118 * Removes {@code elem} from this {@link ListInterface} if it exists. If multiple instances of {@code elem} exist in this {@link ListInterface} the one associated with the smallest index is removed. This method runs in 0(size) time. 119 120 121 122 123 @param elem the element to remove @throws NullPointerException if {@code elem} is {@code null} @throws ItemNotFoundException if {@code elem} is not in the list. */ public void remove(T elem); 124 125 126 127 128 129 130 131 132 133 /** * Returns the smallest index which contains {@code elem}. If there is no * instance of {@code elem} in this {@link ListInterface} then -1 is returned. This method runs in O(size) time. 134 @param elem the element to search for @return the smallest index which contains {@code elem} or -1 if {@code elem} is not in this {@link ListInterface} @throws NullPointerException if {@code elem} is {@code null} 135 136 137 138 public int indexOf(T elem); 139 140 141 142 * Returns {@code true} if this {@link ListInterface} contains no elements and {@code false} otherwise. This method runs in 0(1) time. 143 144 145 146 @return {@code true} if this {@link ListInterface) contains no elements and {@code false} otherwise. */ public boolean isEmpty(); 147 148 149 150 * Returns an Iterator object that will traverse this list. 151 152 153 @return an Iterator object. public Iterator iterator(); 154 155 156 157 } src > app > Node.java >. package app; 1 2 3 4. public class Node { private I data; private Node next; 5 6 7 8 9 10 public Node(T data, Node next) { this.data data; this.next = next; } 11 12 13 public I getData() { return data; } 14 15 16 17 18 19 public Node getNext() { return next; } 20 21 22 public void setData(T data) { this.data = data; } 23 24 25 public void setNext(Node next) { this.next = next; } 26 27 } 28 src > app > RecursiveList.java > RecursiveList > iterator 1 package app; 2 import java.util.Iterator; 4 5 public class RecursiveList implements ListInterface { 3 6 7 8 9 10 private int size; private Node head = null; 11 12 13 public RecursiveList() { this.head = null; this.size = 0; } 14 15 16 17 public Recursivelist(Node first) { this.head = first; this.size = 1; } 18 19 20 21 22 23 @Override public int size() { return size; } 24 25 26 27 @Override public void insertFirst(1 elem) { //TODO: Implement this method. 28 29 } 30 31 32 @Override public void insertLast(elem) { //TODO: Implement this method. 33 } 34 35 36 37 38 39 40 @Override public void insertAt(int index, 1 elem) { //TODO: Implement this method. 41 } 42 43 44 45 46 @Override public I removeFirst() { I removed Item null; //TODO: Implement this method. 47 48 return removedItem; 49 } 50 51 52 @Override public I removeLast() { I removed Item = null; //TODO: Implement this method. 53 54 55 56 return removedItem; } 57 58 59 60 @Override public I removeAt(int i) { I removed Item = null; //TODO: Implement this method. 61 62 63 64 return removedItem; } 65 66 67 68 69 70 71 @Override public I getFirst() { I item = null; //TODO: Implement this method. return item; } 72 73 74 75 76 @Override public I getLast() { I item null; //TODO: Implement this method. 77 78 79 80 return item; 81 } 82 83 84 @Override public I get(int i) { T item = null; //TODO: Implement this method. 85 86 87 return item; 88 89 90 } 91 92 @Override public void remove(t elem) { //TODO: Implement this method. 93 94 95 } 96 96 97 98 @Override public int indexOf(T elem) { int index = -1; //TODO: Implement this method. 99 return index; } 100 101 102 103 104 105 106 107 108 @Override public boolean isEmpty() { boolean empty = false; //TODO: Implement this method. 109 return empty; } 110 111 112 113 114 115 116 117 118 public Iterator iterator() { Iterator iter = null; | // TODO: Implement this method: 119 return iter; ] 120 121 } 122