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 String
s.
Why should we implement our own growable array when we have ArrayList
? I can think of two reasons:
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:
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 emptyWe will implement these together.
Here’s your TODO to complete before we meet again:
ArrayList
. So that I may have time to grade and that you may rest, we will not have lab next week on November 26.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;
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;
}
}
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));
}
}
Leave a Reply