For this assignment, you will extend the ComboList class, which combines features of ArrayLists and LinkedLists. The ComboList class provides the basic behavior of a List using a hybrid data structure: a linked structure with nodes containing ArrayLists. It uses the Node class that was discussed in lectures.
The ComboList class currently has a constructor and two methods implemented: add and sneakPeek. The add method adds a value at the end of the list, adding a new node if the last node is already at capacity. The sneakPeek method prints the contents of the list, separated by nodes (for debugging purposes). Write a driver class that creates a ComboList, adds values to it, and displays the contents. Then, add the following methods to the ComboList class and test them in your driver:
public int size()
public T get(int index)
IndexOutOfBoundsException if the index is invalid). This should be an O(N) operation, but hopefully faster than accessing a traditional linked list due to skipping a Node at a time.
public boolean add(int index, T value)
IndexOutOfBoundsException if the index is invalid). Note that after adding a new value into a Node, the size of the ArrayList in that Node should not exceed the node capacity. If it does, the last value in the ArrayList needs to be moved to the next Node (if space is available) or to a newly inserted Node (if not). This should be an O(N) operation, but hopefully faster than adding to a traditional linked list due to skipping a Node at a time.
public List<T> toList()
List containing all of the elements of the list, in the same order. This should be an O(N) operation.
public String toString()
String representation of the list, separated by commas and contained in square braces. This should be an O(N) operation.
Once you are confident that your methods work, design and implement a driver program to measure the efficiency of the ComboList class when compared with ArrayList and LinkedList. Similar to HW2, your driver should prompt the user for a starting list size and an ending list size. Beginning with the starting size and doubling until the ending size is reached, your driver should create an ArrayList, LinkedList, and ComboList of each size, time how long it takes to perform a get operation on every index and display the times. For example, if the starting index is 1000, the driver would initially construct lists of size 1000 and time 1000 get operations (for indices 0 to 999) on each list. After displaying the times, it should double the list sizes and repeat the process until the ending size is reached.
In a separate document, describe the rate of growth that you would expect to see for each type of list. Provide timings from your driver to support your expectations. How do the timings for ComboList compare with ArrayListand LinkedList?