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 String
s.
Each row of the classroom will take on two 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 emptyPlease 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:
See you next class!
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…
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;
}
}
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;
}
}
Comments