1. What is the running time of the following code?

public static List makeList( int N )

{

ArrayList lst = new ArrayList

for( int i = 0; i < N; i++ )

{ lst.add( i ); lst.trimToSize( );

}

}

(Hint: youll want to research what the trimToSize() call does and how it is implemented.)

2. The following routine removes the first half of the list passed as a parameter:

public static void removeFirstHalf( List lst )

{ int theSize = lst.size() / 2;

for( int i = 0; i < theSize; i++ ) lst. remove( 0 );

}

-Why is theSize saved prior to entering the for loop?

-What is the running time of removeFirstHalf if lst is an ArrayList?

-What is the running time of removeFirstHalf if lst is a LinkedList?

-Does using an iterator make removeFirstHalf faster for either type of List?

3. Suppose we have a reference to a node in a singly linked list that is guaranteed not to be the last node in the list. We do not have references to any other nodes (except by following links). Describe an O(1) algorithm that logically removes the value stored in such a node from the linked list, maintaining the integrity of the list. (Hint: Involve the next node).