public class DoublyLinkedList implements List { private Node head, tail; private int numberOfElements; public DoublyLinkedList() { head = null; tail = null; numberOfElements = 0; } @Override public void addLast(T item) { // TODO } @Override public void addFirst(T item) { // TODO } @Override public T get(int position) { // TODO return null; } @Override public void print() { // TODO } @Override public void printBackwards() { // TODO } @Override public boolean remove(T item) { // TODO return false; } @Override public boolean isEmpty() { // TODO return true; } @Override public int getLength() { // TODO } /** * Inner class representing a node in the linked list */ private class Node { private T data; private Node next, previous; private Node(T data) { this(data,null,null); } private Node (T data, Node next, Node prev) { this.data = data; this.next = next; this.previous = prev; } } } 

////////////////////////////////////////////////////////////////////////////

public class DoublyLinkedListTest { public static void main(String[] args) { // Comment only the test functions you want to run // testPrintEmptyListForward(); // testPrintEmptyListBackward(); // testEmptyGet(); // testAddFirstAndGet(); // testAddFirstForwards(); // testAddFirstBackwards(); // testAddLastAndGet(); // testAddLastForwards(); // testAddLastBackwards(); // testIsEmpty(); // testGetLength(); // testRemoveFromEmptyList(); // testRemoveFromListWithOneElementNegative(); // testRemoveFromListWithOneElementPositive(); // testRemoveFromListWithTwoElementNegative(); // testRemoveFromListWithTwoElementPositive(); // testRemoveFromListWithThreeElementNegative(); // testRemoveFromListWithThreeElementPositive(); // testIterator(); } public static void testPrintEmptyListForward() { //TODO } public static void testPrintEmptyListBackward() { //TODO } public static void testEmptyGet() { List list = new DoublyLinkedList(); System.out.println("The fifth element data in an empty list is " + list.get(5)); } public static void testAddFirstAndGet () { List list = new DoublyLinkedList(); // now add several items to the List list.addFirst("Apple"); list.addFirst("Banana"); list.addFirst("Cherry"); list.addFirst("Donut"); list.addFirst("Donut"); list.addFirst("End"); System.out.println("The sixth element should be Apple, and it is: " + list.get(5)); System.out.println("The fifth element should be Banana, and it is: " + list.get(4)); System.out.println("The fourth element should be Cherry, and it is: " + list.get(3)); System.out.println("The second element should be Donut, and it is: " + list.get(1)); System.out.println("The first element should be End, and it is: " + list.get(0)); } public static void testAddFirstForwards() { System.out.println(""); System.out.println("-------------- testAppendForwards ------------:"); List list = new DoublyLinkedList(); // now add several items to the List list.addFirst("Apple"); list.addFirst("Banana"); list.addFirst("Cherry"); list.addFirst("Donut"); list.addFirst("Donut"); list.addFirst("End"); System.out.println("You should get the list elements in this order: End, Donut, Donut, Cherry, Banana, Apple"); list.print(); System.out.println("--------- End of testAppendForwards -----------:"); } public static void testAddFirstBackwards() { System.out.println(""); System.out.println("-------------- testAppendBackwards ------------:"); List list = new DoublyLinkedList(); // now add several items to the List list.addFirst("Apple"); list.addFirst("Banana"); list.addFirst("Cherry"); list.addFirst("Donut"); list.addFirst("Donut"); list.addFirst("End"); System.out.println("You should get the list elements in this order: Apple, Banana, Cherry, Donut, Donut, End"); list.printBackwards(); System.out.println("--------- End of testAppendBackwards -----------:"); } public static void testIsEmpty() { System.out.println(""); System.out.println("-------------- testIsEmpty ------------:"); List list = new DoublyLinkedList(); System.out.println("isEmpty() should return true, and it is returning " + list.isEmpty()); list.addFirst("One"); System.out.println("isEmpty() should return false, and it is returning " + list.isEmpty()); System.out.println("--------- End of testIsEmpty -----------:"); } public static void testGetLength() { System.out.println(""); System.out.println("-------------- testGetLength ------------:"); List list = new DoublyLinkedList(); System.out.println("getLength() should return 0, and it is returning " + list.getLength()); // now add several items to the List list.addFirst("Apple"); System.out.println("getLength() should return 1, and it is returning " + list.getLength()); list.addLast("Banana"); System.out.println("getLength() should return 2, and it is returning " + list.getLength()); list.addFirst("Cherry"); System.out.println("getLength() should return 3, and it is returning " + list.getLength()); System.out.println("--------- End of testGetLength -----------:"); } public static void testRemoveFromEmptyList() { System.out.println(""); System.out.println("-------------- testRemoveFromEmptyList ------------:"); List list = new DoublyLinkedList(); System.out.println("Nothing to remove from an empty list, to remove() should return false, and it returns " +list.remove("something")); System.out.println("-------------- testRemoveFromEmptyList ------------:"); } public static void testRemoveFromListWithOneElementNegative() { System.out.println(""); System.out.println("-------------- testRemoveFromListWithOneElementNegative ------------:"); List list = new DoublyLinkedList(); list.addFirst("Apple"); System.out.println("remove() should return false, and it returns " +list.remove("something")); System.out.println("-------------- testRemoveFromListWithOneElementNegative ------------:"); } public static void testRemoveFromListWithTwoElementNegative() { System.out.println(""); System.out.println("-------------- testRemoveFromListWithTwoElementNegative ------------:"); List list = new DoublyLinkedList(); list.addFirst("Apple"); list.addFirst("Cherry"); System.out.println("remove() should return false, and it returns " +list.remove("something")); System.out.println("-------------- testRemoveFromListWithTwoElementNegative ------------:"); } public static void testRemoveFromListWithTwoElementPositive() { System.out.println(""); System.out.println("-------------- testRemoveFromListWithTwoElementPositive ------------:"); List list = new DoublyLinkedList(); list.addFirst("Apple"); list.addFirst("Cherry"); System.out.println("remove() should return true, and it returns " +list.remove("Cherry")); System.out.println("You should get the list elements in this order: Apple"); list.print(); System.out.println("-------------- testRemoveFromListWithTwoElementPositive ------------:"); } public static void testRemoveFromListWithOneElementPositive() { System.out.println(""); System.out.println("-------------- testRemoveFromListWithOneElementPositive ------------:"); List list = new DoublyLinkedList(); list.addFirst("Apple"); System.out.println("remove() should return true, and it returns " +list.remove("Apple")); System.out.println("You should get an empty list"); list.print(); System.out.println("-------------- testRemoveFromListWithOneElementPositive ------------:"); } public static void testRemoveFromListWithThreeElementPositive() { System.out.println(""); System.out.println("-------------- testRemoveFromListWithThreeElementPositive ------------:"); List list = new DoublyLinkedList(); list.addLast("Apple"); list.addLast("Cherry"); list.addLast("Banana"); System.out.println("remove() should return true , and it returns " +list.remove("Cherry")); System.out.println("You should get the list elements in this order: Apple, Banana"); list.print(); System.out.println("-------------- testRemoveFromListWithThreeElementPositive ------------:"); } public static void testRemoveFromListWithThreeElementNegative() { System.out.println(""); System.out.println("-------------- testRemoveFromListWithThreeElementNegative ------------:"); List list = new DoublyLinkedList(); list.addLast("Apple"); list.addLast("Cherry"); list.addLast("Banana"); System.out.println("remove() should return false, and it returns " +list.remove("something")); System.out.println("You should get the list elements in this order: Apple, Cherry, Banana"); list.print(); System.out.println("-------------- testRemoveFromListWithThreeElementNegative ------------:"); } public static void testAddLastAndGet () { List list = new DoublyLinkedList(); // now add several items to the List list.addLast("Apple"); list.addLast("Banana"); list.addLast("Cherry"); list.addLast("Donut"); list.addLast("Donut"); list.addLast("End"); System.out.println("The sixth element should be End, and it is: " + list.get(5)); System.out.println("The fifth element should be Donut, and it is: " + list.get(4)); System.out.println("The fourth element should be Donut, and it is: " + list.get(3)); System.out.println("The second element should be Banana, and it is: " + list.get(1)); System.out.println("The first element should be Apple, and it is: " + list.get(0)); } public static void testAddLastForwards() { System.out.println(""); System.out.println("-------------- testAddLastForwards ------------:"); List list = new DoublyLinkedList(); // now add several items to the List list.addLast("Apple"); list.addLast("Banana"); list.addLast("Cherry"); list.addLast("Donut"); list.addLast("Donut"); list.addLast("End"); System.out.println("You should get the list elements in this order: Apple, Banana, Cherry, Donut, Donut, End"); list.print(); System.out.println("--------- End of testAddLastForwards -----------:"); } public static void testAddLastBackwards() { System.out.println(""); System.out.println("-------------- testAddLastBackwards ------------:"); List list = new DoublyLinkedList(); // now add several items to the List list.addLast("Apple"); list.addLast("Banana"); list.addLast("Cherry"); list.addLast("Donut"); list.addLast("Donut"); list.addLast("End"); System.out.println("You should get the list elements in this order: End, Donut, Donut, Cherry, Banana, Apple"); list.printBackwards(); System.out.println("--------- End of testAddLastBackwards -----------:"); } public static void testIterator() { System.out.println(""); System.out.println("-------------- testIterator ------------:"); List list = new DoublyLinkedList(); list.addLast("Apple"); list.addLast("Cherry"); list.addLast("Banana"); //TODO // ADD code to obtain iterator object, then uses it to iterate through the list and print its data. System.out.println("-------------- testIterator ------------:"); } } 

//////////////////////////////////////////////////////////////

public interface List { /** * Adds item to the end of a list * * @param item */ public void addLast(T item); /** * Adds item to the start of a list * * @param item */ public void addFirst(T item); /** * Retrieves item from List * * @param position where 0 is the first position in the list * @return item - the item at the given position on the list * (or null if no item exists at that position) */ public T get (int position); /** * Prints list to screen */ public void print(); /** * Prints list backwards to screen */ public void printBackwards(); /** * Removes first item from List * * @param item * @return true if item was removed, false otherwise */ public boolean remove (T item); /** * Determines if the List is empty. * * @return True if the List is empty, False otherwise. */ public boolean isEmpty(); /** * Determines the number of items in the List * * @return int - The length of the list */ public int getLength(); } 

The Lab Java Files: List.java specifies the interface for a list us .L ing Generics and includes the printBackwards method. . DoublyLinkedListTest.java is a set of tests that test your implementation of the DoublyLinkedList. . DoublyLinkedList.java is a partially completed implementation of the List interface using doubly- linked lists. When you examine DoublyLinkedList.java, you will notice several methods that are not complete (with a comment //TODO), so they only compile, but are lacking a proper implementation. You will implement all methods, and test them using functions that you will add to DoublyLinkedListTest.java main function Step 1. Print an empty list. Implement the print method in the DoublyLinkedList class. You should start from the head, and traverse by the next references. Within the main DoublylinkedListTest.java, finish the function called testPrintEmptyListForward that creates a DoublyLinkedList object calls print on the empty DoublyLinkedList. . Run your main method and make sure it does not crash Step 2. Print an empty list backwards Implement the printBackwards method in the DoublyLinkedList class. You should start from the tail and traverse by the previous references testPrintEmptyListForward that