package deque;

import java.util.ArrayList; import java.util.NoSuchElementException;

public class Deque { /* * Nested inner class, that holds the Nodes of the Deque */ static class Node { int data; Node next; Node prev; public Node(int i) { data = i; next = null; prev = null; } } Node head; //front of the Deque Node tail; //back of the Deque public Deque() { head = null; tail = null; } /* * Returns true if the Deque is empty (contains no Nodes). Returns true otherwise. */ public boolean isEmpty() { return head==null&&tail==null; } /* * Converts an Deque to an ArrayList. * This method is useful for testing. */ public ArrayList toArrayList(){ ArrayList deq = new ArrayList(); Node current = head; while(current!=null) { deq.add(current.data); current = current.next; } return deq; } /* * Returns a String representation of the Deque. * This method is useful for testing. */ public String toString() { String s = ""; if(isEmpty()) return s; Node current = head; while(current!=null) { s = s+current.data + ","; current = current.next; } return s.substring(0,s.length()-1); } /* ******************************************************************************* * * ADD YOUR METHODS HERE * *********************************************************************************/

}

Sorting the Deque (6 points) Implement the following methods. Make sure the method signatures are exactly as described below. public Deque sort (): This method returns a new Deque with the same values as the original Deque, but with the data now in sorted order (from smallest to largest). Testing Your Implementation (6 points) I have given you a very limited set of JUnit tests to help determine if your implementation is correct. You need to add at least 6 more JUnit tests that test typical and edge cases of the different methods. You may want to add more than 6 JUnit tests, but if you add at least 6 JUnit tests (and your program passes them) you will receive full points for this part