24 Javanotes 9.0, Section 7.3 — ArrayList
Section 7.3
ArrayList
As we have just seen in Subsection 7.2.4,
we can easily encode the dynamic array pattern into a class, but it looks like
we need a different class for each data type. In fact, Java has a feature called
“parameterized types” that makes it possible to avoid the multitude of classes, and
Java has a single class named ArrayList that implements the
dynamic array pattern for all data types that are defined as classes (but not,
directly, for primitive types).
7.3.1 ArrayList and Parameterized Types
Java has a standard type with the rather odd name ArrayList<String> that represents
dynamic arrays of Strings. Similarly, there is a type ArrayList<Color>
that can be used to represent dynamic arrays of Colors. And if
Player is a class representing players in a game, then
the type ArrayList<Player> can be used to represent a dynamic
array of Players.
It might look like we still have a multitude of classes here, but in fact there
is only one class, the ArrayList class, defined in the package
java.util. But ArrayList is a
parameterized type. A parameterized type can take a type
parameter, so that from the single class ArrayList,
we get a multitude of types including ArrayList<String>,
ArrayList<Color>, and in fact ArrayList<T>
for any object type T. The type parameter T
must be an object type such as a class name or an interface name. It cannot be
a primitive type. This means that, unfortunately, you can not have an ArrayList of
int or an ArrayList of char.
Consider the type ArrayList<String>. As a type, it can
be used to declare variables, such as
ArrayList<String> namelist;
It can also be used as the type of a formal parameter in a subroutine definition,
or as the return type of a subroutine. It can be used with the new
operator to create objects:
namelist = new ArrayList<String>();
The object created in this way is of type ArrayList<String> and
represents a dynamic list of strings. It has instance methods such as
namelist.add(str) for adding a String to the list,
namelist.get(i) for getting the string at index i,
and namelist.size() for getting the number of items currently in the list.
But we can also use ArrayList with other types.
If Player is a class representing players in a game, we can
create a list of players with
ArrayList<Player> playerList = new ArrayList<Player>();
Then to add a player, plr, to the game, we just have to say
playerList.add(plr). And we can remove player number k
with playerList.remove(k).
Furthermore if playerList is a local variable, then
its declaration can be abbreviated to
var playlerList = new ArrayList<Player>();
using the alternative declaration syntax that was covered in
Subsection 4.8.2. The Java compiler uses the
initial value that is assigned to playerList to deduce that
its type is ArrayList<Player>.
When you use a type such as ArrayList<T>, the compiler will
ensure that only objects of type T can be added to the list.
An attempt to add an object that is not of type T will be
a syntax error, and the program will not compile. However, note that objects
belonging to a subclass of T can be added to the list, since
objects belonging to a subclass of T are still considered to
be of type T. Thus, if class Shape
has subclasses Rectangle, Oval
and RounRect, then a variable of type
ArrayList<Shape> can be used to hold objects of type
Rectangle, Oval, and RoundRect.
(Of course, this is the same way arrays work: An array of type T[]
can hold objects belonging to any subclass of T.)
Similarly, if T is an interface, then any object that
implements interface T can be added to the list.
An object of type ArrayList<T> has all of the instance methods
that you would expect in a dynamic array implementation. Here are some of the most
useful. Suppose that list is a variable of type ArrayList<T>.
Then we have:
-
list.size() — This function returns
the current size of the list, that is, the number of items currently in the list.
The only valid positions in the
list are numbers in the range 0 to list.size()-1. Note that
the size can be zero. A call to the default constructor new ArrayList<T>()
creates a list of size zero. -
list.add(obj) — Adds an object onto
the end of the list, increasing the size by 1. The parameter,
obj, can refer to an object of type T,
or it can be null. -
list.get(N) — This function returns
the value stored at position N in the list. The return type of
this function is T. N
must be an integer in the range 0 to list.size()-1. If
N is outside this range, an error of type IndexOutOfBoundsException
occurs. Calling this function is
similar to referring to A[N] for an array, A, except that you
can’t use list.get(N) on the left side of an assignment statement. -
list.set(N, obj) — Assigns the
object, obj, to position N in the ArrayList,
replacing the item previously stored at position N. The parameter obj
must be of type T. The integer
N must be in the range from 0 to list.size()-1. A
call to this function is equivalent to the command A[N] = obj for an
array A. -
list.clear() — Removes all items from the list, setting its size
to zero. -
list.remove(N) — For an integer,
N, this removes the N-th item in the ArrayList.
N must be in the range 0 to list.size()-1. Any items
in the list that come after the removed item are moved up one position. The
size of the list decreases by 1. This method returns the removed item. -
list.remove(obj) — If the specified
object occurs somewhere in the list, it is removed from the list.
Any items in the list that come after the removed item are moved up one
position. The size of the ArrayList decreases by 1. If obj
occurs more than once in the list, only the first copy is removed. If obj
does not occur in the list, nothing happens; this is not an error. This method
returns a boolean value that says whether or not an item was
actually removed. -
list.indexOf(obj) — A function that
searches for the object, obj, in the list. If the object
is found in the list, then the first position number where it is found is returned.
If the object is not found, then -1 is returned.
For the last two methods listed here, obj is compared to
an item in the list by calling obj.equals(item), unless obj
is null. This means, for example, that strings are tested for equality by checking
the contents of the strings, not their location in memory.
Java comes with several parameterized classes representing different data structures.
Those classes make up the Java Collection Framework. Here we consider
only ArrayList, but we will return to this important topic in
much more detail in Chapter 10.
By the way, ArrayList can also be used as a non-parametrized
type. This means that you can declare variables and create objects of type ArrayList
such as
ArrayList list = new ArrayList();
The effect of this is similar to declaring list to be of type
ArrayList<Object>. That is, list can hold
any object that belongs to a subclass of Object. Since every
class is a subclass of Object, this means that any
object can be stored in list.
7.3.2 Wrapper Classes
As I have already noted, parameterized types don’t work with the primitive types.
There is no such thing as “ArrayList<int>“. However, this limitation
turns out not to be very limiting after all, because of the so-called
wrapper classes such as Integer
and Character.
We have already briefly encountered the classes Double and
Integer in Section 2.5. These classes
contain the static methods Double.parseDouble()
and Integer.parseInteger() that are used to convert strings to
numerical values, and they contain constants such as Integer.MAX_VALUE and Double.NaN.
We have also encountered the Character
class in some examples, with the static method Character.isLetter(),
that can be used to test whether a given value of type char is a
letter. There is a similar class for each of the other primitive types,
Long, Short, Byte,
Float, and Boolean.
These classes are wrapper classes. Although they
contain useful static members, they have another use as
well: They are used for representing primitive type
values as objects.
Remember that the primitive types are not classes, and values of primitive type
are not objects. However, sometimes it’s useful to treat a primitive value
as if it were an object. This is true, for example, when you would like to store
primitive type values in an ArrayList.
You can’t do that literally, but you can “wrap” the
primitive type value in an object belonging to one of the wrapper classes.
For example, an object of type Integer contains a single instance
variable, of type int. The object is a “wrapper”
for the int value. You can get an object that
wraps the int value 42 with
Integer n = Integer.valueOf(42);
The value of n has the same information as the value of type
int, but it is an object. If you want to retrieve the int
value that is wrapped in the object, you can call the function n.intValue().
Similarly, you can wrap a double
in an object of type Double, a boolean value
in an object of type Boolean, and so on. Each wrapper
class has a static valueOf() method for wrapping a primitive type
value in an object.
The method Integer.valueOf() is a static factory method
that returns an object of type Integer.
The Integer class also has a constructor for creating
objects, but it has been deprecated, meaning that it should not be used in new
code and might be removed from the language in the future. The static factory
method has the advantage that if Integer.valueOf()
is called more than once with the same parameter value, it has the option
of returning the same object each time.
This is OK because objects of type Integer are
immutable, that is, the content of the object cannot
be modified after the object has been created. Someone who gets their
hands on an Integer will not be able to
change the primitive int value that it represents. We saw something
similar for the Color
class in Subsection 6.2.1, which also has static factory methods for
creating immutable objects.
To make the wrapper classes even easier to use, there is automatic
conversion between a primitive type and the corresponding wrapper class. For example,
if you use a value of type int in a context that requires an object
of type Integer, the int will automatically be
wrapped in an Integer object. If you say
Integer answer = 42;
the computer will silently read this as if it were
Integer answer = Integer.valueOf(42);
This is called autoboxing. It works in the other direction, too. For example, if
d refers to an object of type Double, you can use d
in a numerical expression such as 2*d. The double value inside
d is automatically unboxed and multiplied by 2. Autoboxing
and unboxing also apply to subroutine calls. For example, you can pass an actual parameter of type
int to a subroutine that has a formal parameter of type Integer,
and vice versa. In fact, autoboxing and unboxing make it possible in many circumstances to ignore the difference
between primitive types and objects.
This is true in particular for parameterized types. Although there is no such thing
as “ArrayList<int>“, there is ArrayList<Integer>.
An ArrayList<Integer> holds objects of type Integer,
but any object of type Integer really just represents an int
value in a rather thin wrapper. Suppose that we have an object of type
ArrayList<Integer>:
ArrayList<Integer> integerList; integerList = new ArrayList<Integer>();
Then we can, for example, add an object to integerList that represents the number 42:
integerList.add( Integer.valueOf(42) );
but because of autoboxing, we can actually say
integerList.add( 42 );
and the compiler will automatically wrap 42 in an object of type Integer
before adding it to the list. Similarly, we can say
int num = integerList.get(3);
The value returned by integerList.get(3) is of type Integer
but because of unboxing, the compiler will automatically convert the return value into an
int, as if we had said
int num = integerList.get(3).intValue();
So, in effect, we can pretty much use integerList as if it were
a dynamic array of int rather than a dynamic array of Integer.
Of course, a similar statement holds for lists of other wrapper classes such as
ArrayList<Double> and ArrayList<Character>.
There is one issue that sometimes causes problems: A list can hold null
values, and a null does not correspond to any primitive type value. This
means, for example, that the statement “int num = integerList.get(3);”
can produce a null pointer exception in the case where integerList.get(3)
returns null. Unless you are sure that all the values in your list are
non-null, you need to take this possibility into account.
7.3.3 Programming With ArrayList
As a simple first example, we can redo ReverseWithDynamicArray.java,
from the previous section, using an
ArrayList instead of a custom dynamic array class. In this case, we want
to store integers in the list, so we should use ArrayList<Integer>.
Here is the complete program:
import textio.TextIO;
import java.util.ArrayList;
/**
* Reads a list of non-zero numbers from the user, then prints
* out the input numbers in the reverse of the order in which
* the were entered. There is no limit on the number of inputs.
*/
public class ReverseWithArrayList {
public static void main(String[] args) {
ArrayList<Integer> list;
list = new ArrayList<Integer>();
System.out.println("Enter some non-zero integers. Enter 0 to end.");
while (true) {
System.out.print("? ");
int number = TextIO.getlnInt();
if (number == 0)
break;
list.add(number);
}
System.out.println();
System.out.println("Your numbers in reverse are:");
for (int i = list.size() - 1; i >= 0; i--) {
System.out.printf("%10d%n", list.get(i));
}
}
}
As illustrated in this example, ArrayLists are commonly processed using
for loops, in much the same way that arrays are processed.
for example, the following loop prints out all the items for a variable namelist of type
ArrayList<String>:
for ( int i = 0; i < namelist.size(); i++ ) {
String item = namelist.get(i);
System.out.println(item);
}
You can also use for-each loops with ArrayLists, so this example could also be written
for ( String item : namelist ) {
System.out.println(item);
}
When working with wrapper classes, the loop control variable in the for-each loop
can be a primitive type variable. This works because of unboxing. For example,
if numbers is of type ArrayList<Double>, then
the following loop can be used to add up all the values in the list:
double sum = 0;
for ( double num : numbers ) {
sum = sum + num;
}
This will work as long as none of the items in the list are null.
If there is a possibility of null values, then you will want to use a loop control
variable of type Double and test for nulls. For example,
to add up all the non-null values in the list:
double sum;
for ( Double num : numbers ) {
if ( num != null ) {
sum = sum + num; // Here, num is SAFELY unboxed to get a double.
}
}
For a more complete and useful example, we will look at the program
SimplePaint2.java. This is a much improved version of
SimplePaint.java from
Subsection 6.3.3.
In the new program, the user can sketch curves in a drawing area
by clicking and dragging with the mouse.
The user can select the drawing color using a menu. The background color of the
drawing area can also be selected using a menu. And there is a “Control”
menu that contains several commands: An “Undo” command, which removes the
most recently drawn curve from the screen, a “Clear” command that removes
all the curves, and a “Use Symmetry” checkbox that turns a symmetry feature
on and off. Curves that are drawn by the user when the symmetry option is on
are reflected horizontally and vertically to produce a symmetric pattern.
(Symmetry is there just to look pretty.)
Unlike the original SimplePaint program, this new version
uses a data structure to store information about the picture that has been
drawn by the user. When the user selects a new background color, the canvas
is filled with the new background color, and all of the curves that were
there previously are redrawn on the new background. To do that, we need to
store enough data to redraw all of the curves. Similarly, the Undo
command is implemented by deleting the data for most recently drawn curve,
and then redrawing the entire picture using the remaining data.
The data structure that we need is implemented using ArrayLists.
The main data for an individual curve consists of a list of the points on the curve. This
data is stored in an object of type
ArrayList<Point2D>.
(Point2D
is standard class in package javafx.geometry:
A Point2D
can be constructed from two double
values, giving the (x,y) coordinates of the point. And
a Point2D
object, pt, has
getter methods pt.getX() and pt.getY()
that return the x and y coordinates.) But in addition to a list of points
on a curve, to redraw the curve, we also need to know its color,
and we need to know whether the symmetry option should be applied to the curve.
All the data that is needed to redraw the curve is grouped into
an object of type CurveData that is defined
as a nested class in the program:
private static class CurveData {
Color color; // The color of the curve.
boolean symmetric; // Are horizontal and vertical reflections also drawn?
ArrayList<Point2D> points; // The points on the curve.
}
However, a picture can contain many curves, not just one, so to store
all the data necessary to redraw the entire picture, we need a list
of objects of type CurveData. For this list,
the program uses an ArrayList, curves, declared as
ArrayList<CurveData> curves = new ArrayList<CurveData>();
Here we have a list of objects, where each object contains a list of
points as part of its data! Let’s look at a few examples of processing
this data structure. When the user clicks the mouse on the drawing surface,
it’s the start of a new curve, and a new CurveData
object must be created to represent that curve. The instance
variables in the new CurveData object must
also be initialized. Here is the code from the mousePressed()
routine that does this, where currentCurve is a global
variable of type CurveData:
currentCurve = new CurveData(); // Create a new CurveData object.
currentCurve.color = currentColor; // The color of a curve is taken from an
// instance variable that represents the
// currently selected drawing color.
currentCurve.symmetric = useSymmetry; // The "symmetric" property of the curve
// is also copied from the current value
// of an instance variable, useSymmetry.
currentCurve.points = new ArrayList<Point2D>(); // A new point list object.
As the user drags the mouse, new points are added to currentCurve,
and line segments of the curve are drawn between points as they are added. When the
user releases the mouse, the curve is complete, and it is added to
the list of curves by calling
curves.add( currentCurve );
When the user changes the background color or selects the “Undo” command,
the picture has to be redrawn. The program has a
redraw()
method that completely redraws the picture. That method uses the data in the
list of CurveData
to draw all the curves. The basic structure is a for-each loop that processes
the data for each individual curve in turn. This has the form:
for ( CurveData curve : curves ) {
.
. // Draw the curve represented by the object, curve, of type CurveData.
.
}
In the body of this loop, curve.points is a variable of
type ArrayList<Point2D>
that holds the list of
points on the curve. The i-th point on the curve can be
obtained by calling the get() method of this list:
curve.points.get(i). This returns a value of type
Point2D which has
getter methods named getX() and getY(). We can refer directly to the
x-coordinate of the i-th point as:
curve.points.get(i).getX()
This might seem rather complicated, but it’s a nice example of a complex name
that specifies a path to a desired piece of data: Go to the object, curve.
Inside curve, go to points. Inside points,
get the i-th item. And from that item, get the x coordinate
by calling its getX() method. Here is the complete definition of the
method that redraws the picture:
private void redraw() {
g.setFill(backgroundColor);
g.fillRect(0,0,canvas.getWidth(),canvas.getHeight());
for ( CurveData curve : curves ) {
g.setStroke(curve.color);
for (int i = 1; i < curve.points.size(); i++) {
// Draw a line segment from point number i-1 to point number i.
double x1 = curve.points.get(i-1).getX();
double y1 = curve.points.get(i-1).getY();
double x2 = curve.points.get(i).getX();
double y2 = curve.points.get(i).getY();
drawSegment(curve.symmetric,x1,y1,x2,y2);
}
}
}
drawSegment() is a method that strokes the line segment
from (x1,y1) to (x2,y2). If the first parameter is
true, it also draws the horizontal and vertical reflections of
that segment.
I have mostly been interested here in discussing how the program uses
ArrayList, but
I encourage you to read the full source code, SimplePaint2.java,
and to try out the program.
In addition to serving as an example of using parameterized types, it also serves
as another example of creating and using menus. You should be able to understand
the entire program.