For this assignment, you will perform experiments with and extend the HybridList class, which combines features of ArrayLists and LinkedLists. The HybridList class provides the basic behavior of a List using a hybrid data structure: a linked structure with nodes containing ArrayLists.

Part 1: Experimentation

The HybridList class currently has two methods implemented: size and add (at the end). It also includes a static main method for comparing the performance of HybridLists with ArrayLists and LinkedLists.

Perform repeated experiments to determine how HybridList compares with the other Lists types when constructing large lists. Provide analysis with statisitcs to support it.

Part 2: Extension

Add the following methods to the HybridList class.

public T get(int index)

Returns the value stored at the specified index. The method should throw an IndexOutOfBoundsException if the index is invalid.

public boolean add(int index, T value)

Adds the value to the list at the specified index and returns true if the add was successful (else false). Note: this may result in an ArrayList within a node exceeding the defaultSize. The method should throw an IndexOutOfBoundsException if the index is invalid.

public List<T> toList()

Returns a List containing all of the elements of the list, in the same order.

public String toString()

Returns a String representation of the list, separated by commas and contained in square braces.

public Iterator<T> iterator()

Returns an Iterator object that enables traversing the list in O(N) time. You will need to define an inner class (similar to the MyArrayList and MyLinkedList examples from lectures) and have the iterator method return an instance of this class. When you have this completed, declare in the class header that HybridList implements the Iterable<T> interface. This will allow for the for-each loop to be used to traverse a HybridList. Note: in order to implement the Iterator interface, your class must implement hasNext, next and remove. For this assignment, it is not necessary to implement the functionality of the remove method - an empty remove is fine.

You will need to define a driver class to test all of the methods you implement. Include this driver class in your submission.