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.
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 HybridList
s with ArrayList
s and LinkedList
s.
Perform repeated experiments to determine how HybridList
compares with the other Lists
types when constructing large lists. Provide analysis with statisitcs to support it.
Add the following methods to the HybridList
class.
public T get(int index)
IndexOutOfBoundsException
if the index is invalid.
public boolean add(int index, T value)
ArrayList
within a node exceeding the defaultSize
. The method should throw an IndexOutOfBoundsException
if the index is invalid.
public List<T> toList()
List
containing all of the elements of the list, in the same order.
public String toString()
String
representation of the list, separated by commas and contained in square braces.
public Iterator<T> iterator()
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.