teaching machines

CS1: Lecture 33 – A Growable Array

November 22, 2019 by Chris Johnson. Filed under cs1, fall 2019, lectures.

Dear students,

Today, November 22, is National Growable Array Day. We will celebrate growable arrays everywhere by growing one of our own growable arrays, right here, in our classroom. I hope you wore your festive gear.

Behind every growable array is an plain old ungrowable array. When that ungrowable array gets filled up, a new and larger ungrowable array is made—containing both the old contents plus some empty cells waiting to be filled. Like the phoenix, the old one dies while the new one takes its place.

The growable array that we use in Java is ArrayList. These growable arrays can hold elements of any object type—but not primitives. For our growable array, we will constrain the problem a bit. We’ll only hold Strings.

Why should we implement our own growable array when we have ArrayList? I can think of two reasons:

• Understanding the magic behind ArrayList can show you that you too can be a magician.
• ArrayList is another of an object, an encapsulation of state and behavior.

Here are some of the behaviors/methods that growable arrays tend to support:

• a constructor, that initializes any state required by the growable array
• get, which returns the element at the given index
• remove, which removes the element at the given index
• add, which adds an element at the end of the list (be careful, the list might be “full”)
• size, which reports how many elements are in the list
• contains, which reports whether or not a list contains the given element
• indexOf, which reports where a given element occurs
• isEmpty, which reports whether or not the list is empty

We will implement these together.

TODO

Here’s your TODO to complete before we meet again:

• Midterm 2 is on Monday, November 25. The structure will be the same as before. During the exam, you may consult one page of hand-written notes that you have made. The topics that we’ve been discussing since the last exam include conditional statements, loops, arrays, and ArrayList. So that I may have time to grade and that you may rest, we will not have lab next week on November 26.
• CS 145, there’s no lab next Tuesday.

See you next class!

Sincerely,

P.S. It’s time for a haiku!

After a big meal
I move to a new body
I know, it is growth

P.P.S. Here’s the code we wrote together…

StringList.java

package lecture1122.cs145;

public class StringList {
  private String[] items;
  private int nextIndex;

  public StringList() {
    items = new String[5];
    nextIndex = 0;
  }

  public void add(String item) {
    if (items.length == nextIndex) {
      String[] newItems = new String[items.length * 2];
      for (int i = 0; i < items.length; i++) {
        newItems[i] = items[i];
      }
      items = newItems;
    }

    items[nextIndex] = item;
    nextIndex++;
  }

  public String get(int i) {
    if (i < nextIndex) {
      return items[i];
    } else {
      throw new IndexOutOfBoundsException(String.format("You done goofed. %d >= %d", i, nextIndex));
    }
  }

  public int size() {
    return nextIndex;
  }

  public void clear() {
    for (int i = 0; i < nextIndex; i++) {
      items[i] = null;
    }
    nextIndex = 0;
  }

  public String remove(int i) {
    String itemToRemove = items[i];
    for (int j = i; j < nextIndex; j++) {
      items[j] = items[j + 1];
    }
    nextIndex--;
    return itemToRemove;
  }
}

StringListTest.java

package lecture1122.cs145;

public class StringListTest {
  public static void main(String[] args) {
    StringList list = new StringList();

    list.add("Umbra");
    list.add("Kongu");
    list.add("Kopaka");
    list.add("Jeff");
    list.add("Hydraxon");
    list.add("Chris");

    list.remove(3);

    for (int i = 0; i < list.size(); i++) {
      System.out.println(list.get(i));
    }

//    list.clear();
//    System.out.println(list.size());

//
//    System.out.println(list.get(0));
//    System.out.println(list.get(1));
  }
}