Understand MyLinkedList class Read MySingleLinkedListclass in MySingleLinkedList.java. Some methods are already implemented with Javadoc comments provided. Finish the unimplemented methods The unimplemented methods have been highlighted and marked as TODO in MySingleLinkedList.java. Extra Credit: two optional exercises are provided for extra credit. To get extra credits, you need: 1. Implement the functions in MySingleLinkedList.java 2. Uncomment the test cases in TestMySingleLinkedList.java 3. You must submit both MySingleLinkedList.java and TestMySingleLinkedList.java to webcat (make a zip file including these two files).

TEST CODE

package lab3; import static org.junit.Assert.*; import org.junit.Before; import org.junit.Test; import java.util.*; public class TestMySingleyLinkedList { private MySingleLinkedList empty ; private MySingleLinkedList one ; private MySingleLinkedList several ; @Before public void setUp() { empty = new MySingleLinkedList() ; one = new MySingleLinkedList() ; one.addFirst(0); several = new MySingleLinkedList() ; several.addFirst(2) ; several.addFirst(1) ; several.addFirst(0) ; } @Test(expected = NoSuchElementException.class) public void testGetFirstException() { empty.getFirst(); } @Test public void testGetFirst() { assertEquals(new Integer(0),one.getFirst()) ; assertEquals(new Integer(0),several.getFirst()) ; } @Test public void testGetLast() { assertEquals(new Integer(0),one.getLast()) ; assertEquals(new Integer(2),several.getLast()) ; } @Test public void testContain() { assertTrue(one.contains(0)) ; assertTrue(several.contains(0)) ; assertTrue(several.contains(1)) ; assertTrue(several.contains(2)) ; } @Test public void testget() { assertEquals(new Integer(0), several.get(0)); assertEquals(new Integer(1), several.get(1)); assertEquals(new Integer(2), several.get(2)); } @Test(timeout = 100) public void testcountApperance() { several.addFirst(2) ; assertEquals(2, several.countApperance(2)); assertEquals(1, several.countApperance(1)); } @Test(timeout = 100) public void testRemove() { assertTrue(several.contains(2)); assertTrue(several.contains(1)); several.remove(1); several.remove(2); assertFalse(several.contains(1)); assertFalse(several.contains(2)); } @Test(timeout = 100) public void testRemoveAll() { assertFalse(several.contains(3)); several.addFirst(2) ; assertTrue(several.contains(2)); several.removeAll(2); assertFalse(several.contains(2)); } //=================== Uncomment the following test cases for Extra Credit Exercises ======================== /* @Test(timeout = 100) public void testinsertBefore() { several.insertBefore(0, 20); assertEquals(new Integer(20), several.getFirst()); } @Test(timeout = 100) public void testReverse() { several.reverse(); assertEquals(new Integer(2), several.getFirst()); assertEquals(new Integer(1), several.get(1)); assertEquals(new Integer(0), several.getLast()); } */ }

CODE TO BE FILLED:

package lab3; /*************************************************************************** * A Linked List class with a private static inner Node class. * *****************************************************************************/ import java.util.*; public class MySingleLinkedList { private Node head; /** * Constructs an empty list */ public MySingleLinkedList() { head = null; } /** * Returns true if the list is empty * @return true/false - empty/not empty */ public boolean isEmpty() { return head == null; } /** * Inserts a new node at the beginning of this list. * @param item - element to add * */ public void addFirst(E item) { head = new Node(item, head); } /** * Returns the first element in the list. * @return the head of the list * @exception NoSuchElementException if an empty list */ public E getFirst() { if(head == null) throw new NoSuchElementException(); return head.data; } /** * Removes the first element in the list. * @return head of the list * */ public E removeFirst() { E tmp = getFirst(); head = head.next; return tmp; } /** * Inserts a new node to the end of this list. * @param item - the element to add at the end of list */ public void addLast(E item) { if( head == null) addFirst(item); else { Node tmp = head; while(tmp.next != null) tmp = tmp.next; tmp.next = new Node(item, null); } } /** * Removes all nodes from the list. * */ public void clear() { head = null; } /** * @return a string representation * */ public String toString() { StringBuffer result = new StringBuffer(); Node tmp = head; while(tmp != null) { tmp = tmp.next; result.append(tmp + " "); } return result.toString(); } /** * Inserts a new node after a node containing the key * @param key - the data of existing node included in the list * @param toInsert - the data of the new node to be inserted */ public void insertAfter(E key, E toInsert) { Node tmp = head; while(tmp != null && !tmp.data.equals(key)) tmp = tmp.next; if(tmp != null) tmp.next = new Node(toInsert, tmp.next); } /* * ================================ The following functions need to be filled =================================================== */ /** * Returns the last element in the list. * @return last element in the list * @throws NoSuchElementException if the list is empty */ public E getLast() { // TODO: please fill your code here. return null; //remove this line after your implementation } /** * Returns true if this list contains the specified element. * @param item - element to be checked * @return True - if contained; otherwise False * */ public boolean contains(E item) { // TODO: please fill your code here. return false; //remove this line after your implementation } /** * Returns the data at the specified position in the list. * @param the position index * @return the data contained at the given position index * @throws IndexOutOfBoundsException if pos is larger than the size of list * */ public E get(int pos) { // TODO: please fill your code here. return null; //remove this line after your implementation } /** * Count the number of occurrence of key * @param key - the element to be counted */ public int countApperance(E key) { int ret = 0; // TODO: Please fill your code here ... return ret; } /** * Removes the first occurrence of the specified element in this list. * @param key - the element to be removed * */ public void remove(E key) { // TODO: please fill your code here. } /** * Removes all the occurrence of the specified element in this list. * @param key - the element to be removed * */ public void removeAll(E key) { // TODO: please fill your code here. } /*************************** Extra Credit Exercises *****************************************/ /***** This is for Extra Credit (3 points) ********************* /** * Inserts a new node before the first appearance of the node containing the key. * @param key the data of existing node included in the list * @param toInsert the data of the new node to be inserted * */ public void insertBefore(E key, E toInsert) { // TODO: please fill your code here. } /***** This is for Extra Credit (5 points) ********************* * Reverses the list: A->B->C to C->B->A * @return the new head */ public Node reverse() { // TODO: please fill your code here. return null; //remove this line after your implementation } /******************************************************* * * The Node class * ********************************************************/ private static class Node { private E data; private Node next; public Node(E data, Node next) { this.data = data; this.next = next; } } }