The collections api - Data Structures and Problem Solving Using Java - page 287

b.

What is the Big-Oh running time if lst is an ArrayList .

What is the Big-Oh running time if lst is a LinkedList .

c.

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<?> lst )
{
lst.subList( 0, lst.size( ) / 2 ).clear( );
}

work, and if so, what is the Big-Oh running time for both an ArrayList
and a LinkedList ?

Static method removeEveryOtherItem removes items in even positions (0,
2, 4, etc.) from a List . One possible implementation of removeEvery-
OtherItem is shown below:

6.17

public static void removeEveryOtherItem( List<?> lst )
{
for( int i = 0; i < lst.size( ); i++ )
lst.remove( i );
}

What is the Big-Oh running time if lst is an ArrayList .

a.

b.

What is the Big-Oh running time if lst is a LinkedList .

c. Suppose we have two computers, Machine A and Machine B.

Machine B is twice as fast as Machine A. Machine A takes 1 sec.
on a 100,000 item list. How large a list can Machine B process in
1 second?

d.

Rewrite removeEveryOtherItem , using an iterator, so that it is effi-
cient for linked lists and does not use any extra space besides the
iterator.

Consider the following implementation of the removeAll method
(which removes all occurrences of any item in the collection passed
as a parameter from this collection).

6.18