Created
February 5, 2015 04:10
-
-
Save samueltcsantos/a8430a7c60081ccbad54 to your computer and use it in GitHub Desktop.
List implementation based on array
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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