» CS 1: Lecture 35 – Implementing a Growable Array

CS 1: Lecture 35 – Implementing a Growable Array

December 6, 2017 by Chris Johnson. Filed under cs1, cs145, cs148, fall 2017, lectures.

Dear students,

Today, December 6, 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. We will constrain the problem a bit: we’ll only hold Strings.

Each row of the classroom will take on two 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

Please write your solutions down on paper, consult with your rowmates, and elect one of you to provide your solution on the board.

Check each other’s work. If your collective solution passes all tests, I’ll grant an extra credit participation point to everyone in attendance.

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

CS 145, your last lab is posted. I advise you to complete it before lab begins, as there will be no next lab. You must also beat a couple of my SplatBot implementations before lab is over.

See you next class!

Sincerely,

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

“What’s already done,
do not do.” But they forget
I am never done

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

StringList.java

package lecture1206;

import java.lang.reflect.Array;

public class StringList {
  int N;
  String [] a;
  
  public StringList () {
    int N = 0;
    String [] a = new String[2];
  }
  
  public void add(String element) {
    if(N >= a.length) {
      String[] b = new String[a.length*2];
      for(int i = 0; i < a.length; i++) {
        b[i] = a[i];
      }
      a = b;
    }
    a[N] = element;
    N++;
    
  }
  
  public void remove(int index) {
    String[] dst = new String[a.length - 1];
    for (int i = 0; i < a.length; i++) {
      if(i < index) {
        dst[i] = a[i];
      }
      if(i > index) {
        dst[i - 1] = a[i];
      }
    }
    a = dst;
    N--;
  }
  public int size() {
    return N;
  }
  public boolean contains(String str) {
    for (int i = 0; i < a.length;++i) {
      if (a[i].equals(str)){
        return true;
      }
    }
    return false;
  }
  public String get(int index) {
    return a[index];
  }
  public boolean isEmpty() {
    return N == 0;
  }
  public int indexOf(String[] s, String a) {
    int counter = 0;
    while (!s[counter].equals(a)) {
      counter++;
    }
    return counter;
}
}

GrowableArray.java

package lecture1206;

public class GrowableArray {

  private String[] currentStringArray;

  public GrowableArray() {
    currentStringArray = new String[10];
  }

  public String get(int i) {
    return currentStringArray[i];
  }

  public boolean isEmpty() {
    for (String s : currentStringArray) {
      if (s != null) {
        return false;
      }
    }
    return true;
  }

  public void remove(int index) {
    String[] newArray = new String[currentStringArray.length - 1];
    for (int i = 0; i < index; i++) {
      newArray[i] = currentStringArray[i];
    }
    for (int i = index; i < newArray.length; i++) {
      newArray[i] = currentStringArray[i + 1];
    }
    currentStringArray = newArray;
  }

  public boolean contains(String string) {
    boolean isTrue = false;
    for (int i = 0; i < currentStringArray.length; i++) {
      if (currentStringArray[i].equals(string)) {
        isTrue = true;
      }
    }
    return isTrue;
  }

  public int indexOf(String s) {
    for (int i = 0; i < currentStringArray.length; i++) {
      if (currentStringArray[i].equals(s)) {
        return i;
      }
    }
    return -1;
  }

  public int size() {
    int length = 0;
    for (int i = 0; i < currentStringArray.length; ++i) {
      if (!get(i).isEmpty()) {
        length++;
      }
    }
    return length;
  }
}

teaching machines