[ Previous Section | Next Section | Chapter Index | Main Index ]

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:

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.

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.4. 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<Point>. (Point is standard class in package java.awt: A Point can be constructed from two int values, giving the (x,y) coordinates of the point. And a Point object, pt, has instance variables x and y representing the coordinates of the point.) 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<Point> 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<Point>();  // 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 paintComponent() 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<Point> 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 Point which has instance variables named x and y. We can refer directly to the x-coordinate of the i-th point as:

curve.points.get(i).x

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 . Here is the complete definition of the method that redraws the picture:

public void paintComponent(Graphics g) {
    super.paintComponent(g);
    Graphics2D g2 = (Graphics2D)g;
    g2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, 
                               RenderingHints.VALUE_ANTIALIAS_ON);
    for ( CurveData curve : curves) {
        g.setColor(curve.color);
        for (int i = 1; i < curve.points.size(); i++) {
                // Draw a line segment from point number i-1 to point number i.
            int x1 = curve.points.get(i-1).x;
            int y1 = curve.points.get(i-1).y;
            int x2 = curve.points.get(i).x;
            int y2 = curve.points.get(i).y;
            g.drawLine(x1,y1,x2,y2);
            if (curve.symmetric) {
                    // Also draw the horizontal and vertical reflections
                    // of the line segment.
                int w = getWidth();
                int h = getHeight();
                g.drawLine(w-x1,y1,w-x2,y2);
                g.drawLine(x1,h-y1,x2,h-y2);
                g.drawLine(w-x1,h-y1,w-x2,h-y2);
            }
        }
    }
} // end paintComponent()

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.

[ Previous Section | Next Section | Chapter Index | Main Index ]