Description
In this assignment, you will use doubly and singly linked lists. You will add new functionality to our original singly linked and doubly linked list implementations. For the second part of the assignment, you will create JUnit tests to make sure that all of your methods are implemented correctly.
Part I - Completing our linked list classes
Required interface
An interface is simply a list of methods (including method signatures) that a particular class must implement. In Java, one can create an interface by using the keyword interface and then specify that a particular class must implement an interface by using the keyword implements. Here, I am using the term "interface" more loosely and giving you the list of required methods in the assignment instead of in an official Java interface file. Make sure the following methods are all implemented in your LinkedList and DLinkedList classes according to the descriptions below:
void addLast(Node<E> n) - add node n to the end of the list.
Node<E> addLast(E e) – create node for e and add to list.
void addFirst(Node<E> n) - add node n to the beginning of the list.
Node<E> addFirst(E e) – create node for e and add to list.
void addBefore(Node<E> loc, Node<E> n) - add n to the list before loc.
Node<E> addBefore(Node<E> loc, E e) – create node for e and add to list.
void addAfter(Node<E> loc, Node<E> n) - add node n after loc.
Node<E> addAfter(Node<E> loc, E e) – create node for e and add to list.
void remove(Node<E> n) - remove node n from the list.
void removeFirst() - remove node n from the list.
void removeLast() - remove node n from the list.
void sort() - sort the list of nodes
Node<E> getFirst() – returns a reference to the head node
Node<E> getLast() – returns a reference to the tail node
int size() – returns the number of nodes in the list
Many of these methods are already implemented. For the DLinkedList class, you need to use DNode<E> instead of Node<E>.
Part II – Unit testing
In unit testing, a program is written to test each method of a class by calling it with a range of inputs and verifying that the method works correctly. Netbeans provides great support for unit testing in Java using the JUnit package. Go ahead and create a JUnit test for all of the methods in your LinkedList and DLinkedList classes by selecting Tools->Create JUnit Tests. You do not need to test the Node and DNode classes. Replace the stub implementations with real implementations that perform meaningful tests of each method to verify that the methods are working correctly.