For the ArrayList Run a timing test to see how long it takes to add items to the
ID: 3756000 • Letter: F
Question
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<E> {
/** 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<E> implements List<E> {
//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<size-1;k++) //shift elements to fill hole
data[k] = data[k+1];
data[size-1] = null; //help garbage collection
size--;
return temp;
}
//utility method
/**checks whether the given index is in the range[0,n-1].*/
protected void checkIndex(int i,int n) throws IndexOutOfBoundsException{
if (i<0 || i>=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 <size; k++)
temp[k] = data[k];
data = temp; //start using new array
}
}
Explanation / Answer
//interface///
/**
* Data Structures & Algorithms 6th Edition
* Goodrick, Tamassia, Goldwasser
* Code Fragments 7.1
*
* An implementation of a simple List interface.
* */
public interface List<E> {
/** 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<E> implements List<E> {
//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<size-1;k++) //shift elements to fill hole
data[k] = data[k+1];
data[size-1] = null; //help garbage collection
size--;
return temp;
}
//utility method
/**checks whether the given index is in the range[0,n-1].*/
protected void checkIndex(int i,int n) throws IndexOutOfBoundsException{
if (i<0 || i>=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 <size; k++)
temp[k] = data[k];
data = temp; //start using new array
}
}