Lists

Because arrays kinda suck.

Arrays

Arrays in Java are fairly primitive:

• Size fixed at creation

• Cannot add or remove elements other than by copying everything up or down

• No methods

Lists

Java has a rich collections library that lives in the package java.util.

We’re going to talk about just two parts of that library: List and ArrayList.

java.util.List

List is an interface which is a thing we’ll talk about in more detail later in the year.

Interfaces

Remember when I said everything in Java is a class?

I lied.

Interfaces are like classes in that they define a new type and a set of methods.

But they (mostly) don’t contain any code that does anything.

java.util.ArrayList

ArrayList is a class.

In fact there’s nothing special about it; you could write it yourself if it didn’t exist as part of Java’s standard library.

It implements the List interface.

There are other classes that implement List.

This is better than Javascript where there’s just one array type.

Don’t reinvent the wheel

If you are about to write a class that seems generally useful, you should check the JDK documentation, Google, or ask a robot to see if there is a class already built into Java that does what you need.

Javadocs

The complete documentation of any class in the JDK can be found in the official Javadocs.

Javadocs document exactly the publicly accessible parts of a class—variables, constructors, and methods—that you need to know about to use it.

Here are the Here are the List Javadocs and the ArrayList Javadocs

What’s this <E> thing?

List is a generic type meaning we can describe the behavior of an List without regard to what particular type of object it might hold.

E is called the type parameter and is a stand-in for the type of element that we will specify and is used in the signature’s of the List methods like this:

boolean add(E e) // add an element of type E to the list

E get(int index) // get an element of type E from the list

Specific List types

• List<String> - contains Strings.

• List<Point> - contains Points.

You can read List<String> as “a List of Strings” just like String[] is “an array of Strings.”

Why?

For the same reason we declare variables to be the specific type of the values we are going to store in them, it’s useful to declare the type of object we intend to put in a given array list. Consider:

List<String> strings = ...;

String upper = strings.get(0);

Because strings is declared to be a List<String> we—and the compiler—know the element returned by get will in fact be a String.

Note the List<E> in the list of “All Implemented Interfaces”.

Declare interfaces, construct classes

List<String> strings = new ArrayList<>();

To the compiler, the variable strings is of type List<String> which means we can only do things with it that are defined in the List<E> interface.

But at runtime it is actually an instance of the class ArrayList so what the list methods actually do is determined by that class.

There are other Lists

List<String> strings = new LinkedList<>();

Creates an instance of a different class that also implements the List interface.

No public variables

Like most well-designed classes, ArrayList has no public instance variables. It also has no static variables.

But it doesn’t really matter because variables are not part of interfaces so if we declare a variable as List<String> we can only do things with it defined in the interface.

Constructing an ArrayList

We only have to specify the type of element when declaring the variable. In the constructor we just need a pair of <>:

List<String> strings = new ArrayList<>(); // ✅

You can redundantly specify it:

List<String> strings = new ArrayList<String>(); // 🆗

Don’t do this as it makes something called a raw type and the compiler will yell at you.

List<String> strings = new ArrayList(); // ☠️☠️☠️:

No-args constructor

You will almost always use the no-argument constructor which constructs an empty array list.

List<String> strings = new ArrayList<>();
List<Integer> numbers = new ArrayList<>();

Copy constructor

There’s another constructor that takes a collection as its argument which can be used to make a new ArrayList that contains the same elements as another:

// Make an ArrayList and add some elements
List<String> strings = new ArrayList<>();
strings.add("a");
strings.add("b");
strings.add("c");

// Make a new ArrayList containing the same elements
List<String> copy = new ArrayList<>(strings);

List.of

Another way to make a list is with the static method List.of:

List<String> strings = List.of("a", "b", "c");

However, the list is not an ArrayList. In fact it is an instance of some unknown-to-us class whose instances are immutable.

Which is often good. Immutability is actually great when you want it.

Copy constructor, part 2

But if we want to make an ArrayList concisely we can combine List.of with the copy constructor:

List<String> foo = new ArrayList<>(List.of("a", "b", "c"));

Makes a new ArrayList containing the strings "a", "b", and "c".

The ArrayList is mutable.

Capacity constructor

If you look at the Javadocs you will see there’s a third constructor that takes an int argument.

List<String> lots = new ArrayList<>(1_000_000);

That constructor makes an ArrayList with an initial underlying array of the given size. But the size() of the ArrayList is still 0.

It’s purely an optimization for when you know you are going to put a lot of elements into an ArrayList as it avoids repeatedly increasing the capacity of the list as you add more items to it.

List methods

Basic methods

E gets filled in

In, for instance, a List<String> these become:

☠️☠️☠️ Raw types ☠️☠️☠️

You can declare a variable as just List. This is called the “raw type” and it can hold any kind of reference type. But you shouldn’t ever use raw types.

Wrapper types

For historical reasons, the type parameters in generic types like List<E> and ArrayList<E> have to be reference types.

ints, doubles, and booleans are not reference types so we can’t make Lists of them.

Instead, Java includes classes called “wrapper types” or “boxed types” that wrap up primitive values to be used with Lists and other generic classes that deal only with objects.

List<Integer>

To make a list of integers we must declare its element type to be Integer.

But luckily something called autoboxing will almost always take care of translating between int and Integer for you.

Autoboxing

List<Integer> nums = new ArrayList<>();
nums.add(42); // boxed into Integer.valueOf(42)
nums.add(100); // boxed into Integer.valueOf(100)

// Boxed values are unboxed so we can use them as
// operands to + which produces an actual `int`.
int sum = nums.get(0) + nums.get(1);

nums.add(sum); // sum is then boxed.

ArrayList vs arrays

Arrays are the only type we can use [] with.

ArrayList is a class so everything we do with it is done with methods.

ArrayLists are mutable both in the sense that we can change individual elements (which we can also do with arrays) but also we can add and remove elements and change the size of the list.

Lists can be mutable or immutable

Not all implementation of List are mutable.

Part of the point of interfaces is they let us pick an implementation that has specific characteristics we care about.

Under the covers

ArrayList is conceptually pretty simple.

Under the covers it’s just using an array to hold its elements.

But it keeps track of how many slots in the array have been used and when it needs to expand, it allocates a new array and copies everything from the old array to the new one and then swaps in the new one.

Array analogs

Note there are no array analogs for add and remove since arrays can’t change size.

Other methods

There are quite a few other useful method that you can look up in the Javadocs.

Loops and Lists

For the next few slides assume we’ve declared and initialized this variable:

List<String> strings

Simple for loop

for (int i = 0; i < strings.size(); i++) {
  doWhatever(strings.get(i));
}

This is just like the canonical for loop over an array except we’ve replaced .length with .size() and [i] with .get(i).

Enhanced for loop

for (String s: strings) {
  doWhatever(s);
}

Lists are written so they can be used with the enhanced for loop.

(You can write your own classes that could be used with the enhanced for loop but doing so is outside the AP curriculum.)

Beyond the AP

ArrayList is a very useful class and in real programs you’d likely take advantage of the many methods described in the Javadocs plus its relation to other classes in the java.util package.