Assignment One

This assignment is to implement the ListHashSet<T> interface. The implementating class must be called LinkedHashTable<T>. Also implement the Iterable<T> interface so that the for-each loop will work. The implementation uses an ArrayList of singly linked lists as the hash table. The data of each node in the singly linked list is a node from a double linked list. The nodes of the doubly linked list hold the data of the LinkedHashTable and the double linked list keeps the insertion order of the elements. The implementation works as follows:

Suppose the class name of the nodes of the singly linked list is Node<E> and the class name of the nodes of the double linked list is DNode<T>. When adding an element x of type T to the LinkedHashTable first calculate the hash address of the element. Then use that as an index into the ArrayList<Node<DNode<T>>> and traverse the corresponding singly linked list looking for x. If x is found do nothing and return false. If x is not found add x to the end of the doubly linked list and add the DNode<T> containing x to the end of the singly linked list. The remove method and the contains method are similar. In this case a picture is worth more than 1000 words and pictures will be drawn in class to illustrate the implementation. Note that the iterator for the doubly linked list only needs to implement nest and hasNext. Also provide a rehash method and rehash when the size of the table is greater than the size of the ArrayList<Node<DNode<T>>>. Provide two constructors, one with no parameters and one with an initial capacity.

Test your implementation with TestLinkedHashTable.java. This assignment is due on Saturday February 25th at 2:00.