AP CSA

ArrayLists

dynamic collections in Java

FRQ

What do you use a lot?

Create an array of 3 things you use a lot — your favorite games, apps, foods, whatever.

Write the Java code. Be ready to share.

Review

We've been using arrays for a while.

What do we know about arrays?

  • Same type — all elements share one data type
  • Indexed — each item has a numbered position
    • What item is at index[0]?
  • Ordered — items stay in the order you placed them
    • Why did you put that particular item at index[1]?
Problem

What is hard with arrays?

What if I want to add one more thing?

Is it impossible or just inconvenient?

Demo

Let's prove it's not impossible ->
Reflect

What did we just do?

Did we actually change the array?

What if we wanted to insert an item into the array?

FRQ

But what about inserting / deleting?

What would you need to do if you wanted to insert something in the middle?

Be specific. What steps would your code take?

The Problem

Insert / Delete in arrays

We can add (though it is a bit of work), and with some more work we'd be able to insert an item into or delete an item from the array by shifting things around.

But the main problem is that we have to create a whole new array to hold the new items. We can't just change the size of the existing one. We didn't change the original array. We made a new one and copied everything into it.

That means:

  • more code
  • more chances for bugs
  • references to the old array don't update
    If our program holds a reference to the original, it won't see the changes.

Before

arr[]
→
a
b
c

After

a
b
c
arr[]
→
a
b
c
d
The Solution

A better way

You know programmers are lazy. If something is annoying to do... we automate it. And you can bet we have automated all of this!

Introducing: the ArrayList

Java has a class that handles all of this work for us. Notice that "Array" in there, there's an array under the hood but we don't have to manage it!

Demo

Let's see it with an ArrayList

Go back to the program we were working on.
We'll rewrite it using ArrayList.

Key Idea

ArrayLists are Objects

The ArrayList object is always the same object. We don't have to replace the list — we just add to it. It updates its own internal array reference so we don't have to.

Normal operation

ArrayList<String>
list
→
ArrayList
object
→
a
b
c

After growth — same object, new internal array

ArrayList<String>
list
→
ArrayList
object
a
b
c
a
b
c
d
Syntax

ArrayLists in Code

Like other objects, you must declare and initialize before use.

JAVA
// Declaration only
ArrayList<String> myStuff;
JAVA
// Declaration and Initialization
ArrayList<String> myStuff = new ArrayList<String>();
JAVA
// Better — Java infers the type in the second <>
ArrayList<String> myStuff = new ArrayList<>();
Real World

A quick note about List

In this class you'll mostly see:

This class
ArrayList<String> myStuff = new ArrayList<>();

In the real world, you'll often see:

Real world
List<String> myStuff = new ArrayList<>();

List is a more general type. Swapping implementations (ArrayList, LinkedList, Vector...) takes just one line.

Swap easily
List<String> myStuff = new Vector<>();
Demo

Using an ArrayList

Let's experiment with a few methods ArrayLists give us.

Let's Go! →
Step by Step

Run the code. What happens?

ERROR in /Main.java (at line 8)
    System.out.println(myPoints);
The local variable myPoints may not have been initialized

Let's fix it by initializing the ArrayList:

Fix
ArrayList myPoints = new ArrayList();
Step by Step

Run again. What happens?

ArrayList is a raw type. References to generic type ArrayList<E> should be parameterized
  • Right now the list can hold anything, but there are a lot of dangers down that path, not the least of which is that it will actually make us write MUCH MORE code to use.
  • We fix it by telling Java what type of data we want to store:
Fix
ArrayList<int> myPoints = new ArrayList<>();
Step by Step

Run again. Now what?

ERROR in /Main.java (at line 6)
    ArrayList<int> myPoints = new ArrayList<>();
Syntax error, insert "Dimensions" to complete ReferenceType
  • This feels like it should work — but it doesn't.
    Why not?
  • Lists must contain objects, not primitives
  • Java thinks you forgot to write int[] (an array of ints). We don't want a list of arrays — we want ints!
Wrapper Classes

You can't have a list of ints.

Lists store objects, not primitives. But Java has our back with object versions of every primitive type:

int→Integer
long→Long
double→Double
char→Character
boolean→Boolean
Fix
ArrayList<Integer> myPoints = new ArrayList<>();

Does it work now?!

add()

FINALLY!!! Now let's add some data

Java
ArrayList<Integer> myPoints = new ArrayList<>();

myPoints.add(3);
myPoints.add(2);
myPoints.add(5);
myPoints.add(1);

System.out.println(myPoints);

Think before you run:

What do you think this will print?

Wait a minute...

What about objects?

I know you are all thinking:
"MrD, you just said ArrayLists can only store objects. But you just added ints to it!"

Java is doing behind-the-scenes work. This is called:

MAGIC!
autoboxing and unboxing.

When Java needs an object, it wraps the int in an Integer "box". When it needs the value back, it unwraps it.

Proof

Let's prove it to ourselves

Java
ArrayList<Integer> myPoints = new ArrayList<>();

myPoints.add(3);
myPoints.add(2);
myPoints.add(5);
myPoints.add(1);

System.out.println(myPoints.get(0) + 5);   // unboxed automatically

System.out.println(myPoints);
set()

Change the data

Java
ArrayList<Integer> myPoints = new ArrayList<>();

myPoints.add(3);
myPoints.add(2);
myPoints.add(5);
myPoints.add(1);

myPoints.set(2, 0);   // index then value

System.out.println(myPoints.get(0) + 5);   // unboxed automatically

System.out.println(myPoints);

Before you run:

What will the list look like?

remove()

Remove some data

Oops, we messed up with that 2:

Java
myPoints.add(3);
myPoints.add(2);
myPoints.add(5);
myPoints.add(1);

myPoints.set(2, 0);   // index then value

myPoints.remove(2);   // removes item at index 2

System.out.println(myPoints.get(0) + 5);   // unboxed automatically

Before you run:

What will the list look like?

remove() — Gotcha

We removed the wrong data

If remove() is given an int, it treats it as an index. If it gets an Integer object, it removes the first matching value.

Java sees a number and assumes you mean an index… unless you explicitly cast:

Fix
myPoints.remove((Integer) 2);
Full code
myPoints.add(3);
myPoints.add(2);
myPoints.add(5);
myPoints.add(1);

myPoints.set(2, 0);

myPoints.remove((Integer) 2);

System.out.println(myPoints.get(0) + 5);   // unboxed automatically
Make sure it's right

When removing:

int → treated as an index Integer → treated as a value
removes index 2
list.remove(2);
removes value 2
list.remove((Integer) 2);
add(index, item)

We can add wherever we want

Java
myPoints.add(3);
myPoints.add(2);
myPoints.add(5);
myPoints.add(1);

myPoints.set(2, 0);   // index then value

myPoints.remove((Integer) 2);   // remove first 2

myPoints.add(4, 1);   // insert 1 at index 4

System.out.println(myPoints.get(0) + 5);   // unboxed automatically
IndexOutOfBoundsException: Index: 4, Size: 3
FRQ

Maybe not anywhere

IndexOutOfBoundsException: Index: 4, Size: 3

We just got an error. I wanted to insert a 4 at index 1.

What happened? Why did the code fail?

Syntax

Index then Value

When adding, you tell it where first, then what:

add to end
list.add(4);
insert at index
list.add(1, 4); // index then value
MCQ

How many items?

What code will tell us how many items are in a list?

  • A myPoints.size()
  • B myPoints.length
  • C myPoints.length()
  • D myPoints.numItems()
A note from Duke

Why the inconsistency?

Array→.length  // field, not a method
String→.length()  // method
List→.size()  // also a method, different name

"Java was built by many teams over many years and we, uh… didn't always coordinate.
Our bad. Just memorize it."

— Duke Duke giving a thumbs up
size()

How many items?

Java
myPoints.add(3);
myPoints.add(2);
myPoints.add(5);
myPoints.add(1);

myPoints.set(2, 0);   // index then value

myPoints.remove((Integer) 2);   // remove first 2

myPoints.add(1, 4);   // index then value

System.out.println(myPoints.get(0) + 5);   // unboxed automatically

System.out.print(myPoints.size());
MCQ

Check yourself

Which correctly creates an empty ArrayList of Strings?

  • A ArrayList<String> list = new ArrayList<>();
  • B ArrayList<String> list;
  • C ArrayList<String> list = new ArrayList();
  • D ArrayList list = new ArrayList<String>();

What is wrong with this code?

Java
ArrayList<int> nums = new ArrayList<>();
  • A ArrayLists cannot store primitives
  • B Missing import
  • C Syntax is wrong
  • D Nothing is wrong
Next Level

What about real objects?

So far we've stored Strings and numbers
but lists can store any object.

Let's work with something a little more interesting.

The Grade Class

Meet the Grade class

Each Grade stores a score and can tell us the letter grade.

Grade.java
public class Grade {

  private double myGrade;

  /** @param score  numeric grade, 0.0–100.0 */
  public Grade(double score) { /* code omitted */ }

  /** @return numeric value 0–100 */
  public double getGrade() { /* code omitted */ }

  /** @return letter grade "A"–"F" */
  public String getLetter() { /* code omitted */ }
}
Using Grade

Build it up

Declare and initialize an ArrayList of Grades:

ArrayList<Grade> grades = new ArrayList<>();

Create a Grade of 100%:

new Grade(100)

Create a random Grade 0–100%:

new Grade(100 * Math.random())

Add that Grade to the list:

grades.add(new Grade(100 * Math.random()));

Add that 28 random Grades to the list:

That's up to you.

The Problem

Using ALL the Grades

How can we print all of the grades? Not like this:

Don't do this
System.out.println(grades);

// [Grade@7d6f77cc, Grade@5aaa6d82, Grade@73a28541,
//  Grade@6f75e721, Grade@69222c14, Grade@606d8acf,
//  Grade@782830e,  Grade@470e2030, Grade@3fb4f649 ...]

We need to use the Grade methods and our old friend: the for loop!

Open Grades Example →
Standard For Loop

Fill in the blank

Java
for ( int i = 0 ; ___ ; i++ ) {
    System.out.println( grades.get(i).getGrade() );
}

What goes in the blank?

What condition should we use?

Hint: how do we know how many elements are in the list?

Enhanced For Loop

There's a cleaner way

Java
for ( ___ g : ___ ) {
    System.out.println( g.getLetter() );
}

What goes in the blanks?

  • Hint: What type is each grade?
  • Hint: What are we looping over?
  • No index needed — Java handles the stepping for you
FRQ

In your own words...

Why do ArrayLists exist if we already have arrays?

What problems do they solve? What trade-offs do they make?