Sunday, September 13, 2015

[Data Structure]ArrayList Implementation



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; 
}

}

No comments:

Post a Comment