Collections vs Fixed Arrays

Instead of a fixed-length array, let’s use the List type. Lists are variable-length sequences of another type T. Here’s how we can declare a List variable and make a list value:

List<Integer> list = new ArrayList<Integer>();

And here are some of its operations:

• indexing: list.get(2)
• assignment: list.set(2, 0)
• length: list.size()

Note that List is an interface (similar to an abstract data type), a type that can’t be constructed directly with new, but that instead specifies the operations that a List must provide. We’ll talk about this notion in a future class on abstract data types. ArrayList is a class, a concrete type that provides implementations of those operations. ArrayList isn’t the only implementation of the List type, though it’s the most commonly used one. LinkedList is another. Check them out in the Java API documentation, which you can find by searching the web for “Java 8 API”. Get to know the Java API docs, they’re your friend. (“API” means “application programmer interface,” and is commonly used as a synonym for “library.”)

Note also that we wrote List<Integer> instead of List<int>. Unfortunately we can’t write List<int> in direct analog to int[]. Lists only know how to deal with object types, not primitive types. In Java, each of the primitive types (which are written in lowercase and often abbreviated, like int) has an equivalent object type (which is capitalized, and fully spelled out, like Integer). Java requires us to use these object type equivalents when we parameterize a type with angle brackets. But in other contexts, Java automatically converts between int and Integer, so we can write Integer i = 5 without any type error.

Here’s the hailstone code written with Lists:

List<Integer> list = new ArrayList<Integer>();
int n = 3;
while (n != 1) {
    list.add(n);
    if (n % 2 == 0) {
        n = n / 2;
    } else {
        n = 3 * n + 1;
    }
}
list.add(n);

Not only simpler but safer too, because the List automatically enlarges itself to fit as many numbers as you add to it (until you run out of memory, of course).

Iterating

// find the maximum point of a hailstone sequence stored in list
int max = 0;
for (int x : list) {
    max = Math.max(x, max);
}