The Lab

Java Files:

List.java specifies the interface for a list using 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.

Within the main DoublyLinkedListTest.java, finish the function called testPrintEmptyListForward that:

creates a DoublyLinkedList object

calls printBackwards on the empty DoublyLinkedList.

Run your main method and make sure it does not crash. Step 3. Get from the doubly-linked list

The get method has an integer parameter that is the position in the list. position start from 0 for the first element. You should return the T data (not the Node) at that position. If the position does not exist, you should return null.

Begin by handling the cases where you should return null. After you are sure the position is valid, write a loop that only traverse as far as the position parameter. Again,

you should return the T data (not the Node) at that position.

Within the main DoublyLinkedListTest.java, write a function called testEmptyGet that works en empty list. Of course, it should return null no matter what position you pass as an argument, since the list is empty.

Step 4a. Prepend to the doubly-linked list: drawing and pseudocode

Draw on paper what it will look like to add a new generic object to the beginning of a doubly-linked list. You should draw three examples:

What happens when you prepend to an empty doubly-linked list?

What happens when you prepend to a doubly-linked list with one item in it?

What happens when you prepend to a doubly-linked list with three items in it?

For each example:

Draw the original doubly-linked list, including (a) the head of the doubly-linked list, (b) the tail of the doubly-linked list, (c) the number of elements, (d) every node in the doubly-linked list, each with the data, next and previous.

Draw the new Node that needs to be created for the new generic object under your original doubly- linked list. Be sure to draw the data, next and previous fields in the Node.

Draw the new arrows necessary for the new doubly-linked list after appending the new Node. Number each of these arrows. Each new arrow will require an assignment in your Java code.

Double-check that the instance variables (the head, tail and the number of elements) are set correctly. If they aren't, you'll need to modify them.

Step 4b. Prepend to the doubly-linked list: Java code.

Implement the addFirst method in the DoublyLinkedList class. The addFirst method adds a new generic object to the start of the doubly linked list.

If you implement addFirst correctly, you should be able to get the output of testPrependAndGet correct by uncommenting it in the main function. If passed, uncommenttestPrependForwards and testPrependBackwards one at a time, to see if you get the list printed in the right order. If not, (or if you get NullPointerException), it is likely that you have corrupted your previous

references.

Step 5a. Append to the doubly-linked list: drawing and pseudocode.

Draw on paper what it will look like to append a new generic object to a doubly-linked list. You should draw three examples:

What happens when you append to an empty doubly-linked list?

What happens when you append to a doubly-linked list with one item in it?

What happens when you append to a doubly-linked list with three items in it?

Step 5b. Append to the doubly-linked list: Java code.

Now implement the addLast method. Be sure your code will handle all three situations that you drew in the previous example. Same way as in 5, uncomment testAddLastAndGet(), testAddLastForwards(), testAddLastBackwards()one at a time, and verify you get the right output.

Step 6. Implement getLength and isEmpty.

Write the getLength() and isEmpty() methods. Since these don't modify the doubly-linked list, they should be very similar to the same methods in the linked list seen in class. Uncomment testIsEmpty() and testGetLength() to verify your code.

Step 7a. Remove from the doubly-linked list: drawing.

First draw on paper what it will look like to remove an object in a doubly-linked list. You will need to search

the entire doubly-linked list for the item you want to version of that item. You should draw five examples least one example):

Assuming you have a doubly-linked list with item in the doubly-linked list?

Assuming you have a doubly-linked list with middle item in the doubly-linked list?

Assuming you have a doubly-linked list with item in the doubly-linked list?

Assuming you have a doubly-linked list with item?

Assuming you have a doubly-linked list with from the doubly-linked list?

Go through the same four-step process as in Step 4a.

remove. If the item is found, you should remove the first (again, have each person in your group should draw at

three items in it, what happens when you remove the first three items in it, what happens when you remove the three items in it, what happens when you remove the last three items in it, what happens if you do not find the

one item in it, what happens when you remove that item

Step 7b. Remove from the doubly-linked list: Java code.

Now implement the remove method. Be sure your code will handle all four situations that you drew in the previous example.

Then you can run the following tests:

testRemoveFromEmptyList(); testRemoveFromListWithOneElementNegative(); testRemoveFromListWithOneElementPositive(); testRemoveFromListWithTwoElementNegative(); testRemoveFromListWithTwoElementPositive(); testRemoveFromListWithThreeElementNegative(); testRemoveFromListWithThreeElementPositive();

and see if they pass the tests properly.

Step8: Iterator for DoublyLinkList

Add an iterator class definition for the DoublyLinkList. Follow the example of the slides. Then finish the testIterator method that create a list, obtain an iterator, and then uses it to print the content of the list.

----------------------------------------------------------------------------------------------------------------------------

HERE's files that given:

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(); }