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