SAMPLE EXAM #4 SOLUTIONS

QUESTION 1:
a) LinkedList is much better for add(0,x);
   ArrayList is must better for get(idx)
   Both ArrayList and LinkedList are bad for remove(x) (they have to find x)
   Both ArrayList and LinkedList are excellent for add(x)

b) Only Sets have efficient contains
   Only Lists allow duplicates
   Both Lists and Sets support add and remove

QUESTION 2:

public boolean contains( String x )
{
    return counts.get( x ) != null;
}

public void add( String x )
{
    Integer occurs = counts.get( x );

    if( occurs == null )
        count.put( x,  1 );
    else
        count.put( x, occurs + 1 );
}

public boolean remove( String X )
{
    Integer occurs = counts.get( x );

    if( occurs == null )
        return false;

    if( occurs == 1 )
        count.remove( x );
    else
        count.put( x, occurs - 1 );

    return true;
}


public int size( )
{
    int total = 0;

    for( int occ : count.values( ) )
        total += occ;

    return total;
}