8.1. Intro to ArrayLists¶
![../_images/lists.jpg](../_images/lists.jpg)
Figure 1: A couple of lists¶
In the last unit, we learned about using arrays to hold collections of related data. However arrays are not very flexible. Most notably, the size of an array is set at the time of creation and cannot be changed.
What if you don’t know how big the collection of data will be? What if you want to both add and remove items from a collection? For example, if you wanted to represent a shopping list, you might add to the list throughout the week and remove things from the list while you are shopping. You probably would not know how many items will be on the list at the beginning of the week. Thus arrays are not a very convenient way to represent a shopping list.
For cases like this, Java provides a wide variety of class collectively referred
to as “collections” classes. In the AP curriculum we will cover one called
ArrayList
which is a re-sizable list. It is called ArrayList
because it
stores the items that have been added to it in an underlying array. But it also
takes care of keeping track of how many items have been added to the array and
it will create a new bigger array under the covers when needed to hold more
items.
You can use ArrayList
instead of arrays whenever you don’t know the size of
the array you need or you know that you will add and remove items and may need
to change the array’s size dynamically during run time. An ArrayList
is
mutable, meaning it can change during run time by adding and removing objects
from it.
Note
An ArrayList
is sometimes called just a list on the CSA exam. Prior to
2020 the AP CSA curriculum included interfaces which are somewhat like
classes and the interface List
was often used to declare a variable that
would refer to an ArrayList
. Interfaces are no longer on the exam, but if
you see List
being used in an old exam question just assume it’s an
ArrayList
.
- An ArrayList will always use less memory than an array.
- No, An ArrayList grows as needed and is typically bigger than the data put into it. If the underlying array in an ArrayList is full when adding in new data, it usually doubles in size.
- An ArrayList can store objects, but arrays can only store primitive types.
- No, you can have an array of objects.
- An ArrayList has faster access to the last element than an array.
- No, an ArrayList is implemented using an array so it has the same access time to any index as an array does.
- An ArrayList resizes itself as necessary as items are added, but an array does not.
- An ArrayList is really a dynamic array (one that can grow or shrink as needed).
7-1-1: Which of the following is a reason to use an ArrayList instead of an array?
8.1.1. Packages and imports¶
To use the ArrayList
class we need to learn a little bit about Java
packages. A package is a set or library of related classes that can be used
in other classes.
The classes we have used until now, such as String
and Math
, are in the
special package java.lang
whose classes are always available in any Java
program.
The ArrayList
class, on the other hand, is defined in a different package,
java.util
. To use classes from packages like java.util
we must either
import them or (much more rarely) refer to them by their full name which
includes the package as a prefix. The full name of ArrayList
is thus
java.util.ArrayList
. But rather than type that out all the time, in any
source file where we want to use ArrayList
we will usually import it with an
import
statement.
Import statements have to come before the class definition in a Java source file
and serve to tell Java which class you mean when you use a short name like
ArrayList
. To import just one class we use a single import
of the
fully-qualified name of the class like this:
// Import just the ArrayList class from java.util
import java.util.ArrayList;
After such an import statement, anywhere ArrayList
is used as a class name
in the file it will be taken to mean java.util.ArrayList
.
Another option is to import all the classes in a package with a “wildcard” import:
// Import everything in java.util including ArrayList
import java.util.*;
This import statement will also cause, ArrayList
to refer
java.util.ArrayList
. But many other names of classes defined in the
java.util
package will also be available whether you use them or not. (One
that you have probably used by now is Scanner
which can be used to read
input a user types at the command line.) Using wildcard imports can cause
conflicts if you import all the classes from two different packages and they
have class names in common but usually that’s not a problem, at least with
packages that are part of Java itself.
Note
Don’t worry about adding import statements on the AP CSA exam. Any that you need will be provided for you.
- You can only have one import statement in a source file.
- You can have an many import statements as you need.
- You must specify the class to import.
- You can use * to import all classes at the specified level.
- Import statements must be before other code in a Java source file.
- Import statements have to be the first Java statements in a source file.
- You must import java.lang.String to use the short name of String.
- You do not have to import any classes that are in the java.lang package.
7-1-2: Which of the following is true about import statements?
8.1.2. Declaring and Creating ArrayLists¶
ArrayList
s are also the first example we’ve seen of a generic type.
They are generic in the sense that we can make ArrayList
s to hold any kind
of object, String
s, Turtle
s, whatever, similar to the way we can
make different kind of arrays to hold different kinds of values.
This means that when we declare an ArrayList
, we use the syntax
ArrayList<Type>
to specify the actual type of the ArrayList
where
Type, called a type parameter, is the type of objects we want to store in
the ArrayList
. For example a variable naming an ArrayList
meant to hold
String
s is declared as ArrayList<String>
as shown in the code below.
Note that when you invoke the constructor you still need the <>
after
ArrayList
but you don’t have to specify the type parameter again—the
compiler can infer it. (You can specify it again if you really want.)
// An ArrayList of Strings:
ArrayList<String> shoppingList = new ArrayList<>();
Note
You can declare a variable to just be of type ArrayList
, with no type
parameter, and then you can put any kind of object at all into it, but it is
good practice to always specify the type of objects you intend to store in an
ArrayList
as it allows the compiler to find errors that would otherwise
be missed until run time.
In the code below we are declaring a variable called nameList
that can
refer to a ArrayList
of strings, but currently doesn’t refer to any
ArrayList
yet as it’s set to null
.
As with other reference types, declaring a ArrayList
variable doesn’t
actually create a ArrayList
object. It only creates a variable that can
refer to a ArrayList
or null
. To actually create a ArrayList
we must
invoke a constructor such as new ArrayList<>()
.
You can get the number of items in a ArrayList
using the size()
method.
Notice that a newly constructed ArrayList
is empty and thus has a size of 0.
Also remember that you can’t call methods on null
so trying to call size
on the value of list2
at line 10 below causes a NullPointerException
.
The following code demonstrates a NullPointerException. Change the list2 declaration so that it creates a new ArrayList to remove the NullPointerException.
You can also create ArrayList
s of integer and double values. However,
ArrayList
s can only hold reference types, not primitive types such as
int
and double
. Thus if we want to represent a list of numbers or
booleans we need to use one of the wrapper classes Integer
, Double
, or
Boolean
as the type parameter. But because of autoboxing, if you declare an
ArrayList<Integer>
, ArrayList<Double>
, or ArrayList<Boolean>
you can
mostly treat the elements of the ArrayList
as if they were in fact int
s, double
s, or boolean
s.
You can actually put in any kind of objects in an ArrayList
, including
instances of classes that you write, such as the Student
, Person
, or
Pet
classes from Unit 5.
Here’s an example of a Integer ArrayList.
- ArrayList[int] numbers = new ArrayList();
- The square brackets [] are only used with arrays, not ArrayLists.
- ArrayList<String> numbers = new ArrayList();
- String is not the correct type since this is for an array of integers, and constructor needs <>s.
- ArrayList<int> numbers = new ArrayList<>();
- ArrayLists cannot hold primitive types like int. You must use the wrapper class Integer.
- ArrayList<Integer> numbers = new ArrayList<>();
- The wrapper class Integer is used to hold integers in an ArrayList.
7-1-6: Which of the following is the correct way to create an ArrayList of integers?
Although it is not on the AP exam, you can convert an array to a List
using
the static method asList
from the Arrays
helper class:
Arrays.asList(arrayname)
. This list will not actually be an ArrayList
but you can pass it to the ArrayList
constructor that takes a collection as
its argument to make a new ArrayList
with the contents of the array.
Note also that ArrayList
has a toString
method that produces a nice
string representation of the contents of the list, unlike the toString
method on arrays which produces not very helpful gibberish like
[Ljava.lang.String;@4361bd48
.
Example code creating an ArrayList from an array.
You can add values to an ArrayList
using its add
method, described in
detail in the next lesson. Try the code below. Note that the type of the
ArrayList
, String
or Integer
, also determines the type of parameters
and return types for all of its methods, so add and print work for any type of
ArrayList
. And when the ArrayList
is a list of Integer
s,
autoboxing takes care of wrapping the int
arguments like 2
and 4
into instances of Integer
for us.
Can you add another item to the shopping list?
8.1.3.
Programming Challenge : FRQ Digits¶
This programming challenge is based on the 2017 Free Response Question part 1a on the 2017 AP CSA
exam. In this question, you are asked to write a constructor for a class called
Digits
. This constructor takes an integer number as its argument and divides
it up into its digits and puts the digits into an ArrayList
. For example,
new Digits(154)
creates an ArrayList with the digits [1, 5, 4].
First, let’s discuss how to break up a number into its digits. Try the code
below. What happens if you divide an integer by 10? Remember that in integer
division the result truncates (cuts off) everything to the right of the decimal
point. Which digit can you get by using % 10
which returns the remainder
after dividing by 10? Try a different number and guess what it will print and
then run to check.
Set number to a different number and guess what number / and % will return. Which operator gives you a digit in number?
We can use a while loop to print out each digit in reverse order starting from the right (4, 5, 1 for the number 154) while dividing it by 10. You can try it in the active code above. Here is the pseudocode:
while number is greater than 0
print out the last digit using %
change the number to cut off the last digit using /
Now, let’s write a constructor for the Digits
class that uses this loop and
adds each found digit to the ArrayList
instead of printing it out. You can
use a special method called Collections.reverse(digitsList);
to reverse the
order of the digits in the ArrayList
after the loop to get them in the right
order. In the next lesson, we will also learn how to use a different add
method that adds in elements at any index instead of the end.
Complete the challenge below to put the digits of a number in an ArrayList.
8.1.4. Summary¶
ArrayList
s are re-sizable lists that allow adding and removing items to change their size during run time.The
ArrayList
class is in thejava.util
package. You must importjava.util.ArrayList
orjava.util.*
to use it.An
ArrayList
object contains object references and is mutable, meaning it can change (by adding and removing items from it).The
ArrayList
constructorArrayList<>()
constructs an empty list of size 0.ArrayList
is really a generic typeArrayList<E>
, where the type parameterE
specifies the type of the elements, likeString
orInteger
that will be stored in a specificArrayList
.ArrayList<E>
is preferred overArrayList
because it allows the compiler to find errors that would otherwise be found at run time.When
ArrayList<E>
is specified, the types of the reference parameters and return type when using its methods are typeE
.ArrayList
s cannot hold primitive types likeint
ordouble
, so you must use the wrapper classesInteger
orDouble
to put numerical values into anArrayList
. However autoboxing usually takes care of that for you.