Skip to content

Instantly share code, notes, and snippets.

@samueltcsantos
Created February 5, 2015 04:10
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save samueltcsantos/a8430a7c60081ccbad54 to your computer and use it in GitHub Desktop.
Save samueltcsantos/a8430a7c60081ccbad54 to your computer and use it in GitHub Desktop.
List implementation based on array
package adt.list;
/**
* List implementation based on Array.
*
* @author Samuel T. C. Santos
* @version 1.0
*
* @param <E>
*/
public class ArrayList<E> implements List<E> {
private E[] data;
private int size = 0;
private static final int CAPACITY = 5;
public ArrayList(){
this(CAPACITY);
}
@SuppressWarnings("unchecked")
public ArrayList(int capacity){
if (capacity <= 0){
throw new IllegalArgumentException("Invalid Capacity!");
}
data = (E[]) new Object[capacity];
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public E get(int i) throws IndexOutOfBoundsException {
checkIndex(i, size);
return data[i];
}
@Override
public E set(int i, E element)
throws NullPointerException, IndexOutOfBoundsException {
if (element == null)
throw new NullPointerException();
checkIndex(i,size);
E temp = data[i];
data[i] = element;
return temp;
}
@Override
public void add(int i, E element)
throws NullPointerException, IndexOutOfBoundsException {
if (element == null)
throw new NullPointerException();
checkIndex(i, size+1);
if (size == data.length){
//throw new IllegalStateException("ArrayList is Full!");
resize(2 * data.length);
}
for (int k=size-1; k >= i; k--){
data[k+1] = data[k];
}
data[i] = element;
size++;
}
@Override
public E remove(int i) throws IndexOutOfBoundsException {
checkIndex(i, size);
E temp = data[i];
for (int k=i; k < size-1; k++){
data[k] = data[k+1];
}
data[size-1] = null;
size--;
return temp;
}
/**
* Resizes internal array to have given capacity >= size.
*/
protected void resize(int capacity){
@SuppressWarnings("unchecked")
E[] temp = (E[]) new Object[capacity];
for (int k=0; k < size; k++){
temp[k] = data[k];
}
data = temp;
}
/**
* Checks whether the given index is in the range [0, n-1].
*
* @param i
* @param size
* @throws IndexOutOfBoundsException
*/
private void checkIndex(int i, int size) throws IndexOutOfBoundsException {
if ( i < 0 || i > size){
throw new IndexOutOfBoundsException("Invalid Index : " + i);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment