public class MyArrayList
{ // COnstructor(), size(), add(), get(), remove(), resize()
private Object[] myStore;
private int actSize = 0;
/*Constructor*/
public MyArrayList()
{
myStore = new Object[10];
}
/*O(1), Get the object given the index*/
public Object get(int index)
{
if (index < actSize)
return myStore[index];
else
throw new ArrayIndexOutOfBoundsException();
}
/*O(1), Add Object into the array Given the Object */
public void add(Object obj)
{
//validate input ?(null allowed), append, size out of bound,
if ( myStore.length - actSize <= 5 )
increaseListSize();
myStore[actSize++] = obj;
}
/*O(n), Remove Object from the array given the index*/
public Object remove(int index)
{
// validate the input, empty or not, reindexing after remove specific index out
// idx 0 1 2 3 4 5
// a b s o l u
// X
// a b “” o l u (nullify)
// a b o l u “” (compact)
if (index < actSize)
{
Obejct obj = myStore[index];
myStore[index] = null;
int tmp = index;
while ( tmp < actSize) // O(n)
{
myStore[tmp]= mySotre[tmp+1];
myStore[tmp+1] = null;
tmp++;
}
actSize--;
return obj;
}
else
{
throw new ArrayIndexOutOfboundsException();
}
}
/* Get the size of the array*/
public int size()
{
return actSize;
}
/* Increase the size of the array when about to exceed the capacity*/
private void increaseListSize()
{
// size make it bigger , but put all the old elements inside it
myStore = Arrays.copyOf(mystore, myStore.length*2);
}
public static int[] copyOf(int[] original, int newLength) {
int[] copy = new int[newLength];
System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
return copy;
}
}
Sunday, September 13, 2015
[Data Structure]ArrayList Implementation
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment