Implement all empty methods. do not change method names, return and parameter types getFirst, getLast, addLast, removeLast, indexOf You need to implement these public class MyLinkedList { Node head; Node tail; int size; public class Node{ T data; Node link; Node(){ } Node(T element){ data = element; link = null; } } MyLinkedList(){ head = null; tail = null; size = 0; } public T getFirst() throws RuntimeException{ // return the first element // if you don't have any element, throw RuntimeException with a message // Write code here } public T getLast() throws RuntimeException{ // return the last element // if you don't have any element, throw RuntimeException with a message // Write code here } public void addLast(T newElement){ // add a new Node to be the last element. // Write code here } public void removeLast(){ // Case 1: if the list is empty --> throw any Exception with a message // Case 2: if you have only one elements // Case 3: in general case // Caution: you must care about the [tail] after removal // Write code here } public int indexOf(T targetElement){ // search the targetElement in the list, return the index of given targetElement if it exists. // if the list doesn't have targetElement, return -1 // Caution: index starts with 0 (the first element's index is 0) // Caution: to return index, you must check the index of node while you searching // Write code here } public Iterator iterator(){ return new Iterator(); } class Iterator { Node next; // to point [next node] object Iterator(){ // next must be the first node of the list next = head; } public T next(){ // return the data_field of [next node] T data_field = next.data; next = next.link; return data_field; } public boolean hasNext(){ // return true when the [next node] exists // return false when we don't have the [next node] if (next != null) { return true; } return false; } } public void removeFirst() throws RuntimeException { if(head == null) { throw new RuntimeException("in removeFirst(): no elements in the list"); } else if(head == tail) { // if(size==1) head = tail = null; size --; } else { head = head.link; size--; } } public void remove(int index) { if(index == 0) { removeFirst(); } else if(head == tail) { head = tail = null; size--; } else { Node cur = head; while (--index > 0) { cur = cur.link; } Node targetNode = cur.link; cur.link = targetNode.link; size--; if(cur.link == null) tail = cur; } } public void addFirst(T newElement){ Node newNode = new Node(newElement); newNode.link = head; head = newNode; if(size==0) { tail = newNode; } size++; } public void add(int index, T newElement) { if(index == 0) addFirst(newElement); else { Node temp1 = head; while (--index > 0) { temp1 = temp1.link; } Node newNode = new Node(newElement); newNode.link = temp1.link; temp1.link = newNode; if (newNode.link == null) { tail = newNode; } size++; } } public String toString() { String str = "["; Node temp = head; while(temp != null) { str = str + temp.data; if(temp != tail) { str = str + ", "; } temp = temp.link; } return str = str + "]"; } } Tester code below=================== public class MyLinkedListTester { public static void printTestName(String str) { System.out.println(); System.out.println("================================="); System.out.println("\t" + str); System.out.println("================================="); } public static void showExceptionMessage(String str) { System.out.println("#################################"); System.out.println("Exception Occurs in Tester [" + "]"); System.out.println("#################################"); System.out.println(); } public static void main(String[] args) { // Checking addFirst() correctly works try { linkedListTester1(); // add first must work because it is given by me. }catch(Exception e) { showExceptionMessage("1"); } // Checking addLast() correctly works try {linkedListTester2();} catch(Exception e) {showExceptionMessage("2");} // Checking add() correctly works try {linkedListTester3();} catch(Exception e) {showExceptionMessage("3");} // Checking removeFirst() correctly works try {linkedListTester4();} catch(Exception e) {showExceptionMessage("4");} // Checking removeLast() correctly works try {linkedListTester5();} catch(Exception e) {showExceptionMessage("5");} // Checking remove() correctly works try {linkedListTester6();} catch(Exception e) {showExceptionMessage("6");} // Checking getFirst() correctly works try {linkedListTester7();} catch(Exception e) {showExceptionMessage("7");} // Checking getLast() correctly works try {linkedListTester8();} catch(Exception e) {showExceptionMessage("8");} // Checking indexOf() correctly works try {linkedListTester9();} catch(Exception e) {showExceptionMessage("9");} // Checking Iterator correctly works try {linkedListIteratorTest1();} catch(Exception e) {showExceptionMessage("Iterator");} } public static void linkedListTester1() { printTestName("[1] addFirst() Tester"); MyLinkedList myList = new MyLinkedList<>(); myList.addFirst("CC"); myList.addFirst("BB"); myList.addFirst("AA"); System.out.println(myList + " <-- Your List"); System.out.println("[AA, BB, CC] <-- Correct List"); } public static void linkedListTester2() { printTestName("[2] addLast() Tester"); MyLinkedList myList = new MyLinkedList<>(); myList.addLast("CC"); myList.addLast("BB"); myList.addLast("AA"); System.out.println(myList + " <-- Your List"); System.out.println("[CC, BB, AA] <-- Correct List"); } public static void linkedListTester3() { printTestName("[3] add() Tester"); MyLinkedList myList = new MyLinkedList<>(); myList.add(0,"DD"); myList.add(0,"CC"); myList.add(0,"BB"); myList.add(3,"EE"); myList.add(0,"AA"); System.out.println(myList + " <-- Your List"); System.out.println("[AA, BB, CC, DD, EE] <-- Correct List"); } public static void linkedListTester4() { printTestName("[4] removeFirst() Tester"); MyLinkedList myList = new MyLinkedList<>(); myList.addFirst("CC"); myList.addFirst("BB"); myList.addFirst("AA"); myList.removeFirst(); myList.removeFirst(); System.out.println(myList + " <-- Your List"); System.out.println("[CC] <-- Correct List 1"); myList.removeFirst(); System.out.println(myList + " <-- Your List"); System.out.println("[] <-- Correct List 1"); } public static void linkedListTester5() { printTestName("[5] removeLast() Tester"); MyLinkedList myList = new MyLinkedList<>(); myList.addFirst("CC"); myList.addFirst("BB"); myList.addFirst("AA"); myList.removeLast(); System.out.println(myList + " <-- Your List"); System.out.println("[AA, BB] <-- Correct List"); myList.removeLast(); myList.removeLast(); System.out.println(myList + " <-- Your List"); System.out.println("[] <-- Correct List"); } public static void linkedListTester6() { printTestName("[6] remove(index) Tester"); MyLinkedList myList = new MyLinkedList<>(); myList.addFirst("CC"); myList.addFirst("BB"); myList.addFirst("AA"); myList.remove(0); System.out.println(myList + " <-- Your List"); System.out.println("[BB, CC] <-- Correct List"); myList.remove(1); System.out.println(myList + " <-- Your List"); System.out.println("[BB] <-- Correct List"); } public static void linkedListTester7() { printTestName("[7] getFirst() Tester"); MyLinkedList myList = new MyLinkedList<>(); myList.addFirst("CC"); myList.addFirst("BB"); myList.addFirst("AA"); System.out.println(myList.getFirst() + " <-- Your element"); System.out.println("AA <-- Correct element"); } public static void linkedListTester8() { printTestName("[8] getLast() Tester"); MyLinkedList myList = new MyLinkedList<>(); myList.addFirst("CC"); myList.addFirst("BB"); myList.addFirst("AA"); System.out.println(myList.getLast() + " <-- Your element"); System.out.println("CC <-- Correct element"); } public static void linkedListTester9() { printTestName("[9] indexOf() Tester"); MyLinkedList myList = new MyLinkedList<>(); myList.addFirst("DD"); myList.addFirst("CC"); myList.addFirst("BB"); myList.addFirst("AA"); System.out.println(myList.indexOf("CC") + " <-- Your element"); System.out.println("2 <-- Correct element"); } public static void linkedListIteratorTest1() { printTestName("Iterator Tester"); MyLinkedList myList = new MyLinkedList<>(); myList.addFirst("JKL"); myList.addFirst("GHI"); myList.addFirst("DEF"); myList.addFirst("ABC"); MyLinkedList.Iterator iter = myList.iterator(); while(iter.hasNext()) { System.out.print(iter.next()+" "); } System.out.println(" <-- Your List"); System.out.println("ABC DEF GHI JKL <-- Correct List"); } }