ArrayList

Array Review

• An array is a collection of similar objects. Actually, one of two things:
  1. A collection of primitives, all of the same type

     int[] integers;
     integers = new int[20];
     

     • The first line declares a reference to an array of ints, called integers.
     • The second line allocates space for an array of twenty ints and makes integers point to this newly allocated array.
  2. A collection of references, all of the same type

     Integer[] integers;
     integers = new Integer[20];
     

     • The first line declares a reference to an array of Integer references, called integers.
     • The second line allocates space for an array of twenty references to Integer objects and makes integers point to this newly allocated array.
     • Each element in the array is currently referencing null since we haven't created any Integer objects.
     • The following loop will create twenty Integer objects and assign the references in the array to point to the newly created Integer objects:

       for(int i=0; i<integers.length; ++i) {
         integers[i] = new Integer(i);
       }
       

• Arrays are nice because they allow you to store a collection of items in a group and act on all of the items in the group in the same way. For example, consider the following method:

  public static void display(String[] names, PrintStream out) {
    for(int i=0; i<names.length; ++i) {
      out.println(names[i]);
    }
  }
  

  • We can call display as follows:

    String[] names = {"Peter", "Paul", "Mary-Anne"};
    display(names, System.out);  // Note: System.out is a PrintStream object
    

  • The method will display all three names. If names had twenty names in it, all twenty would be displayed.
  • If we wanted to do the same thing without an array, we'd need to hard-code the number of names, like this...

    public static void display(String name1, String name2, String name3, PrintStream out) {
      out.println(names1);
      out.println(names2);
      out.println(names3);
    }
    

  • I'm not going to show you what it would look like if we had twenty names because I don't want you to lose your lunch, but just thinking about it probably enough to make you nauseous.
• Arrays are not so nice because they cannot be resized easily. If we need to add an element to an array that is already full, we would need to create a larger array like this:
  1. Create a new, larger, array
  2. Copy over all the primitive values/references in the old array
  3. Reassign the reference to the original array so that it now points to the new array

     /**
       * Resizes an array of Strings
       * @param array Array to be resized
       * @param size Desired size for the array
       * @return A reference to the newly sized array
       */
     public static String[] resize(String[] array, int size) {
       String[] newArray = new String[size];
       // Since the size could be less than array.length, we need to make sure
       //  we only go up to the smaller of the two values.
       for(int i=0; i<array.length && i<size; ++i) {
         newArray[i] = array[i];
       }
       return newArray;
     }
     

• Wait, wouldn't it be nice if we could just start out with an empty array and then just add elements to it as needed? Keep reading because the girls and boys at Sun Microsystems have already fulfilled your wildest dreams!¹⁾

Example Simplified ArrayList Implementation

• The JCF provides a few classes that implement the List<E> interface.
• The ArrayList<E> class.
  • This is basically a souped up array.
  • You can think of this class as containing one field that is a reference to an array and a number of methods that implement the List<E> interface.
  • The actual ArrayList<E> implementation is more involved, but a simplified version of the ArrayList<E> class might look something like this:

    public class ArrayList<E> implements List<E> {
      
      private E[] array = null;
      
      @Override
      public boolean isEmpty() {
        return array!=null;
      }
      
      @Override
      public int size() {
        int size = 0;
        if(array!=null) {
          size = array.length;
        }
        return size;
      }
      
      @SuppressWarnings("unchecked")
      @Override
      public boolean add(E element) {
        E[] temp = (E[])new Object[size()+1];
        for(int i=0; i<size(); ++i) {
          temp[i] = array[i];
        }
        temp[temp.length-1] = element;
        array = temp;
        return true;
      }
      
      @Override
      public E get(int index) {
        checkIndexOutOfBounds(index);
        return array[index];
      }
      
      @Override
      public E set(int index, E element) {
        checkIndexOutOfBounds(index);
        E oldValue = array[index];
        array[index] = element;
        return oldValue;
      }
      
      private void checkIndexOutOfBounds(int index) {
        if(index<0 || index>=size()) {
          throw new IndexOutOfBoundsException("Index: "
              + index + " Size: " + size());
        }
      }
      
      // Other methods of the List interface ...
      
    } // end of ArrayList class
    

  • Again, this is a very simplified version of what really goes on.
  • A more legitimate version of the ArrayList class would not force a new array to be created each time add was called.
  • Instead, it is typical to
    • Create an array that is larger than what is currently required (the size of the array is often referred to as the capacity of the array).
    • An additional attribute is stored in the ArrayList that keeps track of the size of the ArrayList.
    • Whenever add is called, the size is compared with the capacity in order to determine if it is necessary to create a new array.
    • Such an implementation is much more efficient.