Return to lecture notes index

15-100 Lecture 26 (Friday, April 2, 2004)

Java

So far, every array class we've designed, we've inherently been re-doing the same thing - we have an array that holds our Object type (Definition, Collectable, etc.) and methods to add to it, remove Objects from it, etc. Good programmers are lazy and don't like doing the same thing over and over again, so they tend to define Objects that get built into Java (just like String is an Object defined in the Java API) to define these common cases that they find themselves using often.

ArrayList and Vector are two classes built into the Java API that allow us to model dynamic arrays like those we've been designing in class. Today we'll be looking at ArrayList, but note that Vector is largely identical (it was merely added to Java earlier). An ArrayList is similar to an array, but it can be grown past its starting size, things can be added to it, removed from it, it can be compared to other ArrayLists, etc.

Let's say we wanted to build our own generic dynamic array class like ArrayList. What would we do? At its base, we need an array of Objects, because we want a class we can use to make a collection of Definitions, or a collection of Classrooms, or People, or Strings. Remember that all of these are extensions of the Object class in Java, so an array of Objects could hold them all. It could not directly store primitive types (int, double, float, etc.), but we could use the wrapper classes (Integer, Double, Float, etc) to wrap the primitives into Objects:


     int x = 5;
     Integer i = new Integer(x);

The above code wraps the value in int x into an Integer object. This Integer Object could then be added to an array of Objects.

So today we're going to build our own ArrayList class. We'll start by implementing Java's List interface, which defines a set of methods (like add and remove) that all Java lists must support. At heart, our ArrayList class will need a simply array of Objects. We'll also want a variable where we can keep track of the number of Objects stored in the array, because it won't always be equal to the physical size of the array.


     private Object[] arrayList;
     private int count;

Now we need to design the constructors for the ArrayList class. Java's ArrayList class has three of them. One of them initializes the simple array to a default value, defined in the class as a constant. Another allows the user to pass in as an argument the initial size they desire.


     private static final int INITIAL_CAPACITY = 10;

     public ArrayList() {
        arrayList = new Object[INITIAL_CAPACITY];
        count = 0;
     }

     public ArrayList(int initialCapacity) {
        arrayList = new Object[initialCapacity];
        count = 0;
     }

The third constructor in the API accepts a Collection. Collection is an interface in Java that defines a bunch of methods that all collection types in Java should have (examples...). The ArrayList constructor creates an array that is 110% the size of the number of the collection passed in as an argument, so there is room for additional elements to be added without having to expand (or "grow") the array.

Instead of writing a constructor that accepts a Collection, we're going to write one that accepts another ArrayList as an argument, and creates our ArrayList containing the same Objects, but has room for 110% of the elements in the inputted array.


     public ArrayList(ArrayList al) {
        arrayList = new Object[al.length];

        for(int index = 0; index < al.length; index++) {
           arrayList[index] = al.arrayList[index];
           count++;
        }
     }

Now let's start adding methods to our ArrayList, based on those in the Java API (see link at the bottom of the page) version of ArrayList. We'll start with the add() method, which adds a user-specified Object at a user-specified index of the ArrayList.


     // UNWORKING
     public void add(int index, Object element) {
        for(int posn = count; posn > index; posn++) {
           arrayList[posn] = arrayList[posn-1];
        }
     }

The above method will work in the edge cases. For instance, what if the user asks us to insert element at index -1? We must find some way of letting the user know they messed up, such as throwing an exception. If you look at the documentation in the Java API, you will see that ArrayList.add(int index, Object element) throws an IndexOutOfBoundsException in these error cases.


     public void add(int index, Object element) throws IndexOutOfBoundsException {
        if((index < 0) || (index >= al.length))
           throw new IndexOutOfBoundException("Index " + index + " is out of bounds.");

        for(int posn = count; posn > index; posn++) {
           arrayList[posn] = arrayList[posn-1];
        }
     }

If we go back and look at the Java API again, ArrayList has another add method, this one without an index specified as a parameter. It appends the specified Object to the end of the list.


     // UNWORKING
     public boolean add(Object element) {
        for(int index = 0; index < count; index++) {
           newList[index] = arrayList[index];
        }

        newList.count = arrayList.count;		  
     }

But there's a problem here. What if we've run out of space in our array? The ArrayList automatically grows in this case, doubling in length.


     public boolean add(Object element) {
        if(count == arrayList.length) {
           Object[] newList = new Object[2*arrayList.length];

           for(int index = 0; index < count; index++) {
              newList[index] = arrayList[index];
           }

           newList.count = arrayList.count;
        }
     }

Java API

The Java API is the documentation for the set of classes that come "built in" to Java, such as String and ArrayList.

It's a good idea to familiarize yourself with the API and how to navigate around the pages.

The Java 1.4.2 API can be found at:
http://java.sun.com/j2se/1.4.2/docs/api/

You can navigate to the ArrayList part of the documentation by selecting ArrayList from the list of all classes along the lefthand side of the main page.