teaching machines

CS1: Lecture 33 – A Growable Array

November 22, 2019 by . 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:

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

We will implement these together.


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

See you next class!


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…


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;

  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];
    return itemToRemove;


package lecture1122.cs145;

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



    for (int i = 0; i < list.size(); i++) {

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

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