CS1: Lecture 33 – A Growable Array
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
ArrayListcan show you that you too can be a magician. ArrayListis 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 indexremove, which removes the element at the given indexadd, 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 listcontains, which reports whether or not a list contains the given elementindexOf, which reports where a given element occursisEmpty, 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!
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));
}
}