Question: The RandomAccess interface contains no methods but is intended to serve as a marker: a List class implements the interface only if its get and set methods are very efficient. Accordingly, ArrayList implements the RandomAccess interface. Implement static method removeEveryOtherItem, described in Exercise. If list implements RandomAccess (use an instanceof test), then use get and set to reposition items at the front half of the list. Otherwise, use an iterator that is efficient for linked lists.
Exercise: Static method removeHalf removes the first half of a List (if there are an odd number of items, then slightly less than one-half of the list is removed). One possible implementation of removeHalf is shown below:
public static void removeHalf( List lst )
{
int size = lst.size();
for( int i = 0; i < size/2; i++ )
lst.remove( 0 );
}
a. Why can't we use lst.size( )/2 as the test in the for loop?
b. What is the Big-Oh running time if lst is an ArrayList.
c. What is the Big-Oh running time if lst is a LinkedList.
d. Suppose we have two computers, Machine A and Machine B. Machine B is twice as fast as Machine A. How would the running time for removeHalf on Machine B compare to Machine A if Machine B is given an ArrayList that is twice as large as the ArrayList given to Machine A?
e. Does the one line implementation:
public static void removeHalf( List ist )
{
ist.subList( 0, lst.size( ) / 2 ).clear();
}
work, and if so, what is the Big-Oh running time for both an ArrayList and a LinkedList?