Using Arrays

19. Using Arrays

Key concepts

When to use arrays instead of ArrayLists
A non-trivial application of arrays

Motivation

As we pointed out earlier, arrays are a primitive kind of collection. When we create an array, we need to know its size before we do so. Suppose for instance we want the user to input a bunch of weather data. We must allocate the array before the user starts to input the data, but how do we know how much data the user intends to input before they are finished doing so? One solution is to ask the user before they input any data how many items they intend to input, as follows:

int size = input.readInt("How many items?");
double[] rainfall = new double[size];

// now get the items:
for (int day=0; day < size; day++) {
  rainfall[day] = input.readInt("How much rainfall on day " + day);
}

// now the array is full of valid data...

The above works, but if we used an ArrayList, we wouldn't need to worry about "sizing" the ArrayList before adding items to it. ArrayLists resize their capacity dynamically. ArrayLists also allow us to add items to the ArrayList at any location. If we add an item to the middle or front of the ArrayList, the other elements of the ArrayList are shifted appropriately. This is not the case with arrays.

Despite the apparent limitations of arrays, they do provide us with a fundamental building block for creating higher level abstractions. Furthermore, accessing elements in an array is more efficient than the equivalent operations on an ArrayList. While these efficiency considerations should not concern us, they are of concern to programmers who must interface with the services of the system (such as the disk, network devices, audio resources, and so on).

Building our own (simple) ArrayList

To show an application of arrays, imagine that Java does not provide us with the ArrayList class. Using only arrays, we can build our own ArrayList class. We'll implement just the following portion of the interface:

public class SimpleArrayList {
  /** Create a new, empty SimpleArrayList. */
  public SimpleArrayList();

  /** Add the given object to the end of the list. */
  public void add(Object o);

  /** Answer the object that lives at the given index. */
  public Object get(int i);

  /** Answer the number of elements. */
  public int size();
}

Our strategy will be to use an array of Objects internally in our SimpleArrayList class. The array will be used to hold the items that have been added to the SimpleArrayList. For this to work we must also remember how many elements of the array have been set, so that subsequent adds will set the appropriate array element. Let's look at a first cut of an implementation:

public class SimpleArrayList {
  private Object[] items;      // the elements
  private int      size;     // the number of valid elements

  /** Create a new, empty SimpleArrayList. */
  public SimpleArrayList() {
    this.items = new Object[4];
    this.size = 0;
  }

  /** Add the given object to the end of the list. */
  public void add(Object objectToAdd) {
    this.items[this.size] = objectToAdd;
    this.size = this.size + 1;
  }

  /** Answer the object that lives at the given index. */
  public Object get(int index) {
    if (index >= 0 && index < this.size) {
      return this.items[index];
    }
    else {
      return null;
    }
  }

  /** Answer the number of elements. */
  public int size() {
    return this.size;
  }
}

The above implementation works, but only to a point. What happens after we add four elements to the SimpleArrayList? When we attempt to add a fifth element, we'll run out of room in our items array. When this occurs, we need to make more room. To do so, we'll allocate a new array which is twice as large as the original array, set the corresponding elements of the new array to those of the items array, and then rebind the name items to the new array. Let's look at how this works:

public class SimpleArrayList {
  private Object[] items;      // the elements
  private int      size;       // the number of valid elements

  /** Create a new, empty SimpleArrayList. */
  public SimpleArrayList() {
    this.items = new Object[4];
    this.size = 0;
  }

  /** Grow the array, by doubling its size */
  public boolean grow() {
    Object[] newItems = new Object[this.items.length * 2];
    for (int index=0; index < this.items.length; index++) {
      newItems[index] = this.items[index];
    }
    this.items = newItems;
  }

  /** Add the given object to the end of the list. */
  public void add(Object objectToAdd) {
    if (this.size == this.items.length) {
      grow();
    }
    this.items[this.size] = objectToAdd;
    this.size = this.size + 1;
  }

  /** Answer the object that lives at the given index. */
  public Object get(int index) {
    if (index >= 0 && index < this.size) {
      return this.items[index];
    }
    else {
      return null;
    }
  }

  /** Answer the number of elements. */
  public int size() {
    return size;
  }
}

Notice that we've just added a private method that handles the growing of the internal array. It allocates an array twice the size of the old one, sets the elements appropriately, and then rebinds the name items.

The SimpleArrayList class is far from complete. We'd at least like to be able to add an item into the middle of the collection. Imagine how you would do this. First, such a method would perhaps have to grow the items array. Second, it would also need to deal with shifting those items to the "right" (at higher indices) of the insertion point to the right.