/**
  * Unannounced quiz 1.
  * Array-based implementation of the List interface.
  * YOUR NAME:                                YOUR STUDENT ID:
  */
class ArrayList implements List {
	private static final int INITIAL_CAPACITY = 16;
	private Object[] _underlyingStorage;
	
	// The number of elements actually stored in _underlyingStorage
	private int _numElements;

	/** Creates an empty ArrayList with the default initial capacity. */
	public ArrayList () {
		_underlyingStorage = new Object[INITIAL_CAPACITY];
		_numElements = 0;
	}

	/** Adds object o to the end of the list; grow the array as necessary */
	public void add (Object o) {
		if (_underlyingStorage.length == _numElements) {
			Object[] tmp = new Object[_underlyingStorage.length * 2];
			for (int i = 0; i < _underlyingStorage.length; i++) {
				tmp[i] = _underlyingStorage[i];
			}
			_underlyingStorage = tmp;
		}
		_underlyingStorage[_numElements] = o;
		_numElements++;
	}

	/** Retrieves the object stored at the specified index. */
	public Object get (int index) {
		// Write your solution below:
		return _underlyingStorage[index];
	}

	/** Removes the object stored at the specified index. */
	public void remove (int index) {
		for (int i = index + 1; i < _numElements; i++) {
			_underlyingStorage[i-1] = _underlyingStorage[i];
		}
		_numElements--;
	}
}