Write a java generic double-linked list that relies on a head (reference to first element of the list) and tail (reference to the last element of the list). Both are set to null when the list is empty. Both point to the same element when there is only one element in the list. A node structure has only three fields: data and the prev and next references. The class must only define the following entities: an inner class Node, an inner class that implements ListIterator (for the iterator method), head and tail references and an integer representing the list size. However only the hasNext(), next(), hasPrevious() and previous() methods of ListIterator need to be implemented, all other methods can throw the UnsupportedOperationException:

Constructor Summary

BasicDoubleLinkedList()

Method Summary
BasicDoubleLinkedList	addToEnd(T data) Adds an element to the end of the list.
BasicDoubleLinkedList	addToFront(T data) Adds element to the front of the list.
T	getFirst() Returns but does not remove the first element from the list.
T	getLast() Returns but does not remove the last element from the list.
int	getSize() Notice you must not traverse the list to compute the size.
java.util.ListIterator	iterator() This method must be implemented using an inner class that implements ListIterator and defines the methods of hasNext(), next(), hasPrevious() and previous().
BasicDoubleLinkedList	remove(T targetData, java.util.Comparator comparator) Removes the first instance of the targetData from the list.
T	retrieveFirstElement() Removes and returns the first element from the list.
T	retrieveLastElement() Removes and returns the last element from the list.
java.util.ArrayList	toArrayList() Returns an arraylist of the items in the list from head of list to tail of list

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BasicDoubleLinkedList

public BasicDoubleLinkedList() 

Method Detail

getSize

public int getSize() 

Notice you must not traverse the list to compute the size. This method just returns the value of the instance variable you use to keep track of size.

Returns:

the size of the linked list

addToEnd

public BasicDoubleLinkedList addToEnd(T data) 

Adds an element to the end of the list. Do not use iterators to implement this method.

Parameters:

data - the data for the Node within the linked list

Returns:

reference to the current object

addToFront

public BasicDoubleLinkedList addToFront(T data) 

Adds element to the front of the list. Do not use iterators to implement this method.

Parameters:

data - the data for the Node within the linked list

Returns:

reference to the current object

getFirst

public T getFirst() 

Returns but does not remove the first element from the list. If there are no elements the method returns null. Do not implement this method using iterators.

Returns:

the data element or null

getLast

public T getLast() 

Returns but does not remove the last element from the list. If there are no elements the method returns null. Do not implement this method using iterators.

Returns:

the data element or null

iterator

public java.util.ListIterator iterator() throws java.lang.UnsupportedOperationException, java.util.NoSuchElementException 

This method must be implemented using an inner class that implements ListIterator and defines the methods of hasNext(), next(), hasPrevious() and previous(). Remember that we should be able to call the hasNext() method as many times as we want without changing what is considered the next element.

Specified by:

iterator in interface java.lang.Iterable

Throws:

java.util.NoSuchElementException - Your next() method should throw NoSuchElementException if there are no more elements (at the end of the list and calling next() or at the beginning of the list and calling previous()).

java.lang.UnsupportedOperationException - You don't need to implement the ListIterator's remove(), add(), nextIndex() and previousIndex() and set() methods, throw UnsupportedOperationException if called.

remove

public BasicDoubleLinkedList remove(T targetData, java.util.Comparator comparator) 

Removes the first instance of the targetData from the list. Notice that you must remove the elements by performing a single traversal over the list. You may not use any of the other retrieval methods associated with the class in order to complete the removal process. You must use the provided comparator (do not use equals) to find those elements that match the target. Do not implement this method using iterators.

Parameters:

targetData - the data element to be removed

comparator - the comparator to determine equality of data elements

Returns:

data element or null

retrieveFirstElement

public T retrieveFirstElement() 

Removes and returns the first element from the list. If there are no elements the method returns null. Do not implement this method using iterators.

Returns:

data element or null

retrieveLastElement

public T retrieveLastElement() 

Removes and returns the last element from the list. If there are no elements the method returns null. Do not implement implement this method using iterators.

Returns:

data element or null

toArrayList

public java.util.ArrayList toArrayList() 

Returns an arraylist of the items in the list from head of list to tail of list

Returns:

an arraylist of the items in the list