CODE HERE:

import java.util.AbstractList; import java.util.Collection;

/** * This is a copy of the JCF class ArrayList. It implements the List * interface as a single array a. Elements are stored at positions * a[0],...,a[size()-1]. Doubling/halving is used to resize the array * a when necessary. * @author morin * * @param the type of objects stored in the List */ public class BlockedList extends AbstractList { /** * keeps track of the class of objects we store */ Factory f;

/** * The number of elements stored */ int n;

/** * The block size */ int b;

/** * Constructor * @param t the type of objects that are stored in this list * @param b the block size */ public BlockedList(Class t, int b) { f = new Factory(t); n = 0; // TODO: Implement this }

public int size() { return n; }

public T get(int i) { // TODO: Implement this if (i n - 1) throw new IndexOutOfBoundsException(); return null; }

public T set(int i, T x) { // TODO: Implement this if (i n - 1) throw new IndexOutOfBoundsException(); return null; }

public void add(int i, T x) { // TODO: Implement this if (i n) throw new IndexOutOfBoundsException(); }

public T remove(int i) { // TODO: Implement this if (i n - 1) throw new IndexOutOfBoundsException(); return null; } }

1. Implement a Block edL st class that implements the List interface. You may use any of the classes in JCF or in the textbook code. The constructor for this class takes an integer block size and the implementation should have these perfomance characteristics: 1. get(i) and set(i,x) should run in O(1) time per operation 2 add(1, x) and remove (i) should run in O( b + min( i , n- )/ b) amortized time per operation