For the ArrayList

Run a timing test to see how long it takes to add items to the ArrayList just before, at, and just after the ArrayList has to double it data array size (see example below).

Start you test at n slightly less than 2^27 (i.e. 134,217,728) and then for each additional test double the starting value for n.

Keep increasing the starting value of n until you run out of memory.

Write your test so your program does not crash when it runs out of memory.

Use the nanosecond timer instead of the millisecond timer.

Use an ArrayList of Booleans to minimize memory requirements.

What i have for ArrayList:

///interface///

/** * Data Structures & Algorithms 6th Edition * Goodrick, Tamassia, Goldwasser * Code Fragments 7.1 * * An implementation of a simple List interface. * */

public interface List { /** Returns number of elements in the list*/ int size(); /**Returns whether the list is empty*/ boolean isEmpty(); /** Returns element at index i*/ E get(int i) throws IndexOutOfBoundsException; /** Replaces element at index i with e,returns replaced element*/ E set(int i,E e) throws IndexOutOfBoundsException; /**Inserts element at index i, shifting all other elements*/ void add(int i,E e) throws IndexOutOfBoundsException; /** Removes and returns element an index i then shift other elements*/ E remove(int i) throws IndexOutOfBoundsException; }

///ArrayList///

/** * Data Structures & Algorithms 6th Edition * Goodrick, Tamassia, Goldwasser * Code Fragments 7.2, 7.3, 7.4 and 7.5 * * An implementation of a simple ArrayList class. * */ public class ArrayList implements List { //instance variables public static final int CAPACITY=16; private E[] data; private int size=0; //constructors public ArrayList(){ this(CAPACITY); } public ArrayList(int capacity){ data = (E[])new Object[capacity]; } //public methods /**Returns number of elements in the array list*/ @Override public int size(){ return size; } /** returns whether the list is empty*/ @Override public boolean isEmpty(){ return (size==0); } /**Returns element at index i*/ @Override public E get(int i) throws IndexOutOfBoundsException{ checkIndex(i,size); return data[i]; } /**Replaces element at index i with e, returns replaced*/ @Override public E set(int i,E e) throws IndexOutOfBoundsException{ checkIndex(i,size); E temp = data[i]; data[i] = e; return temp; } /** Inserts element e to be at index i shifting other elements*/ @Override public void add(int i,E e) throws IndexOutOfBoundsException{ checkIndex(i,size + 1); if (size== data.length) //not enough capacity resize(2 * data.length); //so double current capacity for (int k = size-1;k>=i;k--) //start by shifting rightmost data[k+1] = data [k]; data[i]= e; //ready to place new element size++; } /** removes/returns number at index i and shifts elements*/ @Override public E remove(int i) throws IndexOutOfBoundsException{ checkIndex(i, size); E temp = data[i]; for (int k=i;k=n) throw new IndexOutOfBoundsException("Illegal index: "+i); } /** Resizes internal array to have given capacity >=size.*/ protected void resize(int capacity){ E[] temp = (E[]) new Object[capacity]; //safe cast; compiler may give warning for (int k=0; k