ArrayLists

Roughly the material from 7.1, 7.2, and 7.3.

An example of a normal JDK class

Most of your Java programming will have to do with using classes, the ones provided by Java as well as the ones you write.

For the most part there’s nothing special about the ones that come with Java except that you don’t have to write them.

(The JDK is the “Java Development Kit”, basically everything that comes with Java, the language.)

Classes we’ve officially learned so far

The main thing about classes

There’s nothing you can do with them but construct them, access their variables (instance and static) and call their methods (instance and static), and compare them with == and !=.

Therefore …

To know how to use a class you just need to know what constructors, variables, and methods it has.

And most classes don’t have public variables except for static constants like Math.PI and Color.RED.

There are many classes in Java

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

ChatGPT knows what’s up

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 ArrayList Javadocs

What’s this ArrayList<E>?

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

The <E> is a stand-in for the type of element that we will specify.

Specific ArrayList types

• ArrayList<String> - contains Strings.

• ArrayList<Point> - contains Points

You can read ArrayList<X> as “an ArrayList of Xs” just like X[] is “an array of Xs.”

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:

ArrayList<String> strings = ...;

strings.get(0).indexOf("x")

Because strings is declared to be an ArrayList<String> we know the element returned by get will in fact be a String and will have an indexOf method.

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

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

Finally, wrapper types have a purpose!!!

ints and doubles are not objects so we can’t make an ArrayList of them.

This is finally where we actually need to use the wrapper types Integer and Double.

ArrayList<Integer>

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

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

Autoboxing

ArrayList<Integer> nums = ...;
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 +. Result is then an int.
int sum = nums.get(0) + nums.get(1);

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

ArrayLists 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.

Variables

As is usual, ArrayList has no public instance variables. It also has no static variables.

If you look closely at the Javadocs you’ll see it does have a single field (another name for variables in a class) called modCount. You can ignore that.

Constructors

Constructing an ArrayList

We have to specify the type of element when declaring the variable, but we don’t have to specify it again in the call to the constructor.

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

Though you can specify it if you really want:

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

No-args constructor

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

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

Copying 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:

ArrayList<String> strings = new ArrayList<>();
strings.add("a");
strings.add("b");
strings.add("c");
ArrayList<String> copy = new ArrayList<>(strings);

Capacity constructor

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

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

That constructor makes an ArrayList with an initial underlying array of the given size.

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.

Methods

ArrayList methods.

These are the methods you need to know for the AP exam.

Array analogues

Other methods

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

Loops and ArrayLists

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

ArrayList<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);
}

ArrayLists 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 it outside the AP curriculum.)

Removing in a loop

Suppose we want to remove items matching some criteria from an ArrayList.

We need to check all the elements of the list so that suggests we need a loop.

But we need to be a bit careful about how we iterate through the loop since when we remove an item from a list all the items to the right (at greater indices) shift down one index.

for loop to remove things

for (int i = 0; i < strings.size(); i++) {
  if (dontLikeThisOne(strings.get(i))) {
     strings.remove(i);
     // The element that was at i + 1 is now at i,
     // so on the next iteration of the loop we'd
     // end up skipping that element. So we decrement
     // i here so after the i++ we're back to the
     // current value of i.
     i--;
  }
}

A normal for loop except doing a thing that is generally frowned upon, namely modifying the loop variable inside the loop itself. But in this case it’s necessary to compensate.

while loop to remove things

int i = 0;
while (i < strings.size()) {
  if (dontLikeThisOne(strings.get(i))) {
     strings.remove(i);
  } else {
    i++;
  }
}

Similar to the for loop on the previous slide but because we have to update the loop variable in the loop body, we only do it when we actually need to move forward.

Looping backwards

for (int i = strings.size() - 1; i >= 0; i--) {
  if (dontLikeThisOne(strings.get(i))) {
    strings.remove(i);
  }
}

Possibly the cleanest. A canonical backwards for loop and we don’t have to adjust the index because when we remove an element the things at greater indices shift down but we’re moving on to a yet lower index.

Will also do slightly less copying while shifting things down.

Summary

For the AP curriculum this is pretty much all you need to know plus how to use what’s covered here in some standard algorithms, many of which we’ve already discussed in the context of arrays.

Make sure you are clear about the differences and similarities between ArraryLists (a class, can change size, manipulated with methods) and arrays (built into the language, fixed-size, manipulated with special syntax.)

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 Javadoc plus its relation to other classes in the java.util package.