Doubly Linked List Lab

Create a class DoublyLinkedList which has a generic type E and subclasses the abstract LabTemplate class. In DoublyLinkedList, you must implement every abstract method defined in the LabTemplate class. You do not need to implement any other methods. The class header for DoublyLinkedList should be as follows:

 public class DoublyLinkedList extends LabTemplate{} 

Youll notice that the LabTemplate class defines instance variables of type Node. The node class is provided for you. You do not need to implement your own node class.

Some points about the lab:

When adding an element to the head or tail of a list: create a new node with the given

element, set the head or tail instance variable to the new node, set the new nodes next and previous instance variables to the appropriate values, and increase the size instance variable.

If a node does not have a next or pervious node (for example, the last node in the linked list does not have a next node), the value of its next or pervious instance variable should be null

If the linked list is empty, the head and tail instance variables should be null

If the linked list has a single element, the head and tail instance variables should both

be set to the single node. But the nodes next and previous instance variables should

both be null.

When removing a node, we delink the node from the linked list. For example, if we

want to remove the head node: we should get the second node in the linked list, set that node to the head variable, set the value of the new heads previous instance variable to null, set the value of the hold heads next instance variable to null, and get the element stored in the old head and return it.

_______ Node.java ________

 public class Node { //Instance Variables private E element; private Node next; private Node previous; //Parameterized Constructor public Node(E anElement, Node previousNode, Node nextNode) { element = anElement; next = nextNode; previous = previousNode; } //Getters and setters public E getElement() { return element; } public void setElement(E anElement) { element = anElement; } public Node getNextNode(){ return next; } public void setNextNode(Node nextNode) { next = nextNode; } public Node getPreviousNode(){ return previous; } public void setPreviousNode(Node nextNode) { previous = nextNode; } public String toString() { return element.toString(); } } _______________________ DoublyLinkedListTest.java _______________________ 

import static org.junit.Assert.*; import org.junit.Test; public class DoublyLinkedListTest { //Test that it subclasses the lab template @Test public void SubclassTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); boolean isSubclassed = myLinkedList instanceof LabTemplate; assertEquals("When checking if the DoublyLinkedList class subclasses the given LabTemplate class, we",true,isSubclassed); } //Test the isEmpty function (it should be zero using the default constructor) @Test public void IsEmptyTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); boolean isEmpty = myLinkedList.isEmpty(); assertEquals("When checking if a newly created DoublyLinkedList object is empty using the isEmpty mathod, we",true,isEmpty); } //Test default size is zero @Test public void EmptyListSizeTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); int listSize = myLinkedList.getSize(); assertEquals("When checking the size of a newly created DoublyLinkedList object using the getSize method, we",0,listSize); } //Test that default head and tail nodes are null @Test public void EmptyListHeadAndTail() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); String headValue = myLinkedList.getFirst(); String tailValue = myLinkedList.getLast(); assertEquals("When checking the head of a newly created DoublyLinkedList object using the getFirst method, we",null,headValue); assertEquals("When checking the tail of a newly created DoublyLinkedList object using the getLast method, we",null,tailValue); } //Test addFirst function (add two elements) @Test public void addFirstTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); myLinkedList.addFirst(500); myLinkedList.addFirst(100); Node testingNode = myLinkedList.getHeadNode(); assertEquals("When checking the first node we",100,testingNode.getElement().intValue()); testingNode = testingNode.getNextNode(); assertEquals("When checking the second node we",500,testingNode.getElement().intValue()); } //Test addLast function (add two elements) @Test public void addLastTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); myLinkedList.addLast(500); myLinkedList.addLast(100); Node testingNode = myLinkedList.getHeadNode(); assertEquals("When checking the first node we",500,testingNode.getElement().intValue()); testingNode = testingNode.getNextNode(); assertEquals("When checking the second node we",100,testingNode.getElement().intValue()); } //Test getFirst @Test public void getFirstTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); myLinkedList.addFirst(500); myLinkedList.addFirst(300); myLinkedList.addFirst(100); Integer element = myLinkedList.getFirst(); assertEquals("When checking the first node we",100,element.intValue()); } //Test getLast @Test public void getLastTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); myLinkedList.addFirst(500); myLinkedList.addFirst(300); myLinkedList.addFirst(100); Integer element = myLinkedList.getLast(); assertEquals("When checking the last node we",500,element.intValue()); } //Test isEmpty and Size with elements in the LinkedList @Test public void SizeAndEmptyWithElementsTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); myLinkedList.addFirst(500); myLinkedList.addFirst(300); myLinkedList.addFirst(100); int size = myLinkedList.getSize(); boolean isEmpty = myLinkedList.isEmpty(); assertEquals("When checking the size we",3,size); assertEquals("When checking if the Linked List was empty we",false,isEmpty); } //Test removeFirst @Test public void removeFirstTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); //Add three elements myLinkedList.addFirst(500); myLinkedList.addFirst(300); myLinkedList.addFirst(100); //Remove the first myLinkedList.removeFirst(); //Check the size of the list, and the node values. First should be 300, second should be 500 Node currentNode = myLinkedList.getHeadNode(); assertEquals("When checking LinkedList size we",2,myLinkedList.getSize()); assertEquals("When checking the isEmpty function we",false,myLinkedList.isEmpty()); assertEquals("When checking the value of the first node in the list we",300,currentNode.getElement().intValue()); currentNode = currentNode.getNextNode(); assertEquals("When checking the value of the second node in the list we",500,currentNode.getElement().intValue()); } //Test removeLast @Test public void removeLastTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); //Add three elements myLinkedList.addFirst(500); myLinkedList.addFirst(300); myLinkedList.addFirst(100); //Remove the first myLinkedList.removeLast(); //Check the size of the list, and the node values. First should be 300, second should be 500 Node currentNode = myLinkedList.getHeadNode(); assertEquals("When checking LinkedList size we",2,myLinkedList.getSize()); assertEquals("When checking the isEmpty function we",false,myLinkedList.isEmpty()); assertEquals("When checking the value of the first node in the list we",100,currentNode.getElement().intValue()); currentNode = currentNode.getNextNode(); assertEquals("When checking the value of the second node in the list we",300,currentNode.getElement().intValue()); } //Add single element to the linked list and test if the node is the head and tail. (Use get head node to test the node itself) @Test public void CheckHeadAndTailWithSingleElementTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); //Add one element myLinkedList.addFirst(500); assertEquals("When checking the value of the Linked List's head we",500,myLinkedList.getFirst().intValue()); assertEquals("When checking the value of the Linked List's tail we",500,myLinkedList.getLast().intValue()); Node currentNode = myLinkedList.getHeadNode(); assertEquals("When checking the value of the Linked List's single node we",500,currentNode.getElement().intValue()); assertEquals("When checking the \"next\" value of the node, we",null,currentNode.getNextNode()); assertEquals("When checking the \"previous\" value of the node, we",null,currentNode.getPreviousNode()); } //Add several elements and check if the head and tail are correct @Test public void CheckHeadAndTailWithMultipleElementsTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); //Add one element myLinkedList.addFirst(500); myLinkedList.addFirst(400); myLinkedList.addFirst(300); myLinkedList.addFirst(200); myLinkedList.addFirst(100); myLinkedList.addFirst(0); assertEquals("When checking the value of the Linked List's head we",0,myLinkedList.getFirst().intValue()); assertEquals("When checking the value of the Linked List's tail we",500,myLinkedList.getLast().intValue()); Node currentNode = myLinkedList.getHeadNode(); assertEquals("When checking the value of the Linked List's head node we",0,currentNode.getElement().intValue()); assertEquals("When checking the \"next\" value of the node, we",100,currentNode.getNextNode().getElement().intValue()); assertEquals("When checking the \"previous\" value of the node, we",null,currentNode.getPreviousNode()); currentNode = currentNode.getNextNode(); currentNode = currentNode.getNextNode(); currentNode = currentNode.getNextNode(); currentNode = currentNode.getNextNode(); currentNode = currentNode.getNextNode(); assertEquals("When checking the value of the Linked List's tail node we",500,currentNode.getElement().intValue()); assertEquals("When checking the \"next\" value of the node, we",null,currentNode.getNextNode()); assertEquals("When checking the \"previous\" value of the node, we",400,currentNode.getPreviousNode().getElement().intValue()); } //Use getHeadNode to make sure we can traverse the list properly @Test public void NodeConnectionTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); //Add one element myLinkedList.addFirst(500); myLinkedList.addFirst(400); myLinkedList.addFirst(300); myLinkedList.addFirst(200); myLinkedList.addFirst(100); myLinkedList.addFirst(0); assertEquals("When checking the value of the Linked List's head we",0,myLinkedList.getFirst().intValue()); assertEquals("When checking the value of the Linked List's tail we",500,myLinkedList.getLast().intValue()); Node currentNode = myLinkedList.getHeadNode(); assertEquals("When checking the value of the Linked List's head node we",0,currentNode.getElement().intValue()); assertEquals("When checking the \"next\" value of the node, we",100,currentNode.getNextNode().getElement().intValue()); assertEquals("When checking the \"previous\" value of the node, we",null,currentNode.getPreviousNode()); currentNode = currentNode.getNextNode(); assertEquals("When checking the value of the Linked List's next node we",100,currentNode.getElement().intValue()); assertEquals("When checking the \"next\" value of the node, we",200,currentNode.getNextNode().getElement().intValue()); assertEquals("When checking the \"previous\" value of the node, we",0,currentNode.getPreviousNode().getElement().intValue()); currentNode = currentNode.getNextNode(); assertEquals("When checking the value of the Linked List's next node we",200,currentNode.getElement().intValue()); assertEquals("When checking the \"next\" value of the node, we",300,currentNode.getNextNode().getElement().intValue()); assertEquals("When checking the \"previous\" value of the node, we",100,currentNode.getPreviousNode().getElement().intValue()); currentNode = currentNode.getNextNode(); assertEquals("When checking the value of the Linked List's next node we",300,currentNode.getElement().intValue()); assertEquals("When checking the \"next\" value of the node, we",400,currentNode.getNextNode().getElement().intValue()); assertEquals("When checking the \"previous\" value of the node, we",200,currentNode.getPreviousNode().getElement().intValue()); currentNode = currentNode.getNextNode(); assertEquals("When checking the value of the Linked List's next node we",400,currentNode.getElement().intValue()); assertEquals("When checking the \"next\" value of the node, we",500,currentNode.getNextNode().getElement().intValue()); assertEquals("When checking the \"previous\" value of the node, we",300,currentNode.getPreviousNode().getElement().intValue()); currentNode = currentNode.getNextNode(); assertEquals("When checking the value of the Linked List's tail node we",500,currentNode.getElement().intValue()); assertEquals("When checking the \"next\" value of the node, we",null,currentNode.getNextNode()); assertEquals("When checking the \"previous\" value of the node, we",400,currentNode.getPreviousNode().getElement().intValue()); } //Test getElementAt @Test public void GetElementAtInvalidTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); //Add one element myLinkedList.addFirst(500); myLinkedList.addFirst(400); myLinkedList.addFirst(300); myLinkedList.addFirst(200); myLinkedList.addFirst(100); myLinkedList.addFirst(0); boolean exceptionThrown = false; try { myLinkedList.getElementAt(-1); } catch(IndexOutOfBoundsException e) { exceptionThrown = true; } finally { assertTrue("Index was too small and expected an IndexOutOfBounds exception to be thown but none was",exceptionThrown); } exceptionThrown = false; try { myLinkedList.getElementAt(10); } catch(IndexOutOfBoundsException e) { exceptionThrown = true; } finally { assertTrue("Index was too large and expected an IndexOutOfBounds exception to be thown but none was",exceptionThrown); } } @Test public void GetElementAtValidIndexsTest() { DoublyLinkedList myLinkedList = new DoublyLinkedList(); //Add one element myLinkedList.addFirst(500); myLinkedList.addFirst(400); myLinkedList.addFirst(300); myLinkedList.addFirst(200); myLinkedList.addFirst(100); myLinkedList.addFirst(0); assertEquals("For element 0 we",0,myLinkedList.getElementAt(0).intValue()); assertEquals("For element 1 we",100,myLinkedList.getElementAt(1).intValue()); assertEquals("For element 2 we",200,myLinkedList.getElementAt(2).intValue()); assertEquals("For element 3 we",300,myLinkedList.getElementAt(3).intValue()); assertEquals("For element 4 we",400,myLinkedList.getElementAt(4).intValue()); assertEquals("For element 5 we",500,myLinkedList.getElementAt(5).intValue()); } }