Java ArrayList data types

The ArrayList class is a Java class that you can use to store lists of objects. You can also store objects in an array, but arrays have a couple of obvious problems.

• To create an array, you have to specify a size for the array. Sometimes you won't know what size array you will need at the instant you create the array.
• Although it is possible to resize arrays by creating a new, larger array and copying data over from the old array, doing this is clunky and awkward.

The primary goal of the Java ArrayList class is to provide a class that replicates many of the features of arrays, while adding some new features that are designed to work around the problems listed above.

Basics of ArrayLists

To create an ArrayList object you use the following syntax.

Here Type is the type that you are planning to store in the ArrayList. For example, to make an ArrayList that can hold Strings you would do

A fundamental limitation of ArrayLists is that they can only hold objects, and not primitive types such as ints.

The workaround for this is that Java provides a class equivalent for every one of the primitive types. For example, there is an Integer class corresponding to the int type and a Double class corresponding to the double type, and so on. The first step to being able to store a list of ints in an ArrayList is to instead create an ArrayList that can hold a list of Integer objects:

When you create an ArrayList, the list you get is initially empty. To add new items to the end of the ArrayList you use the add() method:

Adding items to an ArrayList of Integers is similar:

An alternative way to add ints to an ArrayList is to use the autoboxing feature. This feature automatically converts primitive types into their object equivalents:

To retrieve items from an ArrayList, use the get() method.

To determine the size of an ArrayList, use the size() method.

To replace an existing value with a new value, use the set() method:

Along with being to add items and have the list resize automatically to accomodate them, you can also remove items and have the list shrink automatically each time you remove an item. To remove an item, use the remove() method with the index of the item you want to remove. For example, to remove the last item in an ArrayList you would do

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.

Java has a standard type with the rather odd name ArrayList<String> that represents dynamic arrays of Strings. Similarly, there is a type ArrayList<Button> that can be used to represent dynamic arrays of Buttons. 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<Button>, 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

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:

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

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 (in Java 10 or later) to

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, for example, a variable of type ArrayList<Pane> can be used to hold objects of type BorderPane, TilePane, GridPane, or any other subclass of Pane. (Of course, this is the same way arrays work: An object 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.
• 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.
• 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

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.

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 Double contains a single instance variable, of type double. The object is a "wrapper" for the double value. You can create an object that wraps the double value 6.0221415e23 with

The value of d contains the same information as the value of type double, but it is an object. If you want to retrieve the double value that is wrapped in the object, you can call the function d.doubleValue(). Similarly, you can wrap an int in an object of type Integer, a boolean value in an object of type Boolean, and so on.

Actually, instead of calling the constructor, new Double(x), it is preferable to use the static method Double.valueOf(x), which does essentially the same thing; that is, it returns an object of type Double that wraps the double value x. The advantage is that if Double.valueOf() is called more than once with the same parameter, value, it has the option of returning the same object each time. After the first call with that parameter, it can reuse the same object in subsequent calls with the same parameter. This is OK because objects of type Double are immutable, so two objects that start out with the same value are guaranteed to be identical forever. Double.valueOf is a kind of "factory method" like those we saw for Color and Font in Section 6.2. Each of the wrapper classes has a similar factory method: Integer.valueOf(n), Character.valueOf(ch), and so on.

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

the computer will silently read this as if it were

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

Then we can, for example, add an object to integerList that represents the number 42:

but because of autoboxing, we can actually say

and the compiler will automatically wrap 42 in an object of type Integer before adding it to the list. Similarly, we can say

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

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

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:

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

You can also use for-each loops with ArrayLists, so this example could also be written

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:

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:

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 a 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 a point. 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:

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

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

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

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

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:

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:

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.

Page 2

Two array processing techniques that are particularly common are searching and sorting. Searching here refers to finding an item in the array that meets some specified criterion. Sorting refers to rearranging all the items in the array into increasing or decreasing order (where the meaning of increasing and decreasing can depend on the context). We have seen in Subsection 7.2.2 that Java has some built-in methods for searching and sorting arrays. However, a computer science student should be familiar with the algorithms that are used in those methods. In this section, you will learn some algorithms for searching and sorting.

Sorting and searching are often discussed, in a theoretical sort of way, using an array of numbers as an example. In practical situations, though, more interesting types of data are usually involved. For example, the array might be a mailing list, and each element of the array might be an object containing a name and address. Given the name of a person, you might want to look up that person's address. This is an example of searching, since you want to find the object in the array that contains the given name. It would also be useful to be able to sort the array according to various criteria. One example of sorting would be ordering the elements of the array so that the names are in alphabetical order. Another example would be to order the elements of the array according to zip code before printing a set of mailing labels. (This kind of sorting can get you a cheaper postage rate on a large mailing.)

This example can be generalized to a more abstract situation in which we have an array that contains objects, and we want to search or sort the array based on the value of one of the instance variables in the objects. We can use some terminology here that originated in work with "databases," which are just large, organized collections of data. We refer to each of the objects in the array as a record. The instance variables in an object are then called fields of the record. In the mailing list example, each record would contain a name and address. The fields of the record might be the first name, last name, street address, state, city and zip code. For the purpose of searching or sorting, one of the fields is designated to be the key field. Searching then means finding a record in the array that has a specified value in its key field. Sorting means moving the records around in the array so that the key fields of the record are in increasing (or decreasing) order.

In this section, most of my examples follow the tradition of using arrays of numbers. But I'll also give a few examples using records and keys, to remind you of the more practical applications.

There is an obvious algorithm for searching for a particular item in an array: Look at each item in the array in turn, and check whether that item is the one you are looking for. If so, the search is finished. If you look at every item without finding the one you want, then you can be sure that the item is not in the array. It's easy to write a subroutine to implement this algorithm. Let's say the array that you want to search is an array of ints. Here is a method that will search the array for a specified integer. If the integer is found, the method returns the index of the location in the array where it is found. If the integer is not in the array, the method returns the value -1 as a signal that the integer could not be found:

This method of searching an array by looking at each item in turn is called linear search. If nothing is known about the order of the items in the array, then there is really no better alternative algorithm. But if the elements in the array are known to be in increasing or decreasing order, then a much faster search algorithm can be used. An array in which the elements are in order is said to be sorted. Of course, it takes some work to sort an array, but if the array is to be searched many times, then the work done in sorting it can really pay off.

Binary search is a method for searching for a given item in a sorted array. Although the implementation is not trivial, the basic idea is simple: If you are searching for an item in a sorted list, then it is possible to eliminate half of the items in the list by inspecting a single item. For example, suppose that you are looking for the number 42 in a sorted array of 1000 integers. Let's assume that the array is sorted into increasing order. Suppose you check item number 500 in the array, and find that the item is 93. Since 42 is less than 93, and since the elements in the array are in increasing order, we can conclude that if 42 occurs in the array at all, then it must occur somewhere before location 500. All the locations numbered 500 or above contain values that are greater than or equal to 93. These locations can be eliminated as possible locations of the number 42.

The next obvious step is to check location 250. If the number at that location is, say, -21, then you can eliminate locations before 250 and limit further search to locations between 251 and 499. The next test will limit the search to about 125 locations, and the one after that to about 62. After just 10 steps, there is only one location left. This is a whole lot better than looking through every element in the array. If there were a million items, it would still take only 20 steps for binary search to search the array! (Mathematically, the number of steps is approximately equal to the logarithm, in the base 2, of the number of items in the array.)

In order to make binary search into a Java subroutine that searches an array A for an item N, we just have to keep track of the range of locations that could possibly contain N. At each step, as we eliminate possibilities, we reduce the size of this range. The basic operation is to look at the item in the middle of the range. If this item is greater than N, then the second half of the range can be eliminated. If it is less than N, then the first half of the range can be eliminated. If the number in the middle just happens to be N exactly, then the search is finished. If the size of the range decreases to zero, then the number N does not occur in the array. Here is a subroutine that implements this idea:

One particularly common application of searching is with association lists. The standard example of an association list is a dictionary. A dictionary associates definitions with words. Given a word, you can use the dictionary to look up its definition. We can think of the dictionary as being a list of pairs of the form (w,d), where w is a word and d is its definition. A general association list is a list of pairs (k,v), where k is some "key" value, and v is a value associated to that key. In general, we want to assume that no two pairs in the list have the same key. There are two basic operations on association lists: Given a key, k, find the value v associated with k, if any. And given a key, k, and a value v, add the pair (k,v) to the association list (replacing the pair, if any, that had the same key value). The two operations are usually called get and put.

Association lists are very widely used in computer science. For example, a compiler has to keep track of the location in memory associated with each variable. It can do this with an association list in which each key is a variable name and the associated value is the address of that variable in memory. Another example would be a mailing list, if we think of it as associating an address to each name on the list. As a related example, consider a phone directory that associates a phone number to each name. We'll look at a highly simplified version of this example. (This is not meant to be a realistic way to implement a phone directory!)

The items in the phone directory's association list could be objects belonging to the class:

The data for a phone directory consists of an array of type PhoneEntry[] and an integer variable to keep track of how many entries are actually stored in the directory. The technique of dynamic arrays (Subsection 7.2.4) can be used in order to avoid putting an arbitrary limit on the number of entries that the phone directory can hold. Using an ArrayList would be another possibility. A PhoneDirectory class should include instance methods that implement the "get" and "put" operations. Here is one possible simple definition of the class:

The class defines a private instance method, find(), that uses linear search to find the position of a given name in the array of name/number pairs. The find() method is used both in the getNumber() method and in the putNumber() method. Note in particular that putNumber(name,number) has to check whether the name is in the phone directory. If so, it just changes the number in the existing entry; if not, it has to create a new phone entry and add it to the array.

This class could use a lot of improvement. For one thing, it would be nice to use binary search instead of simple linear search in the getNumber method. However, we could only do that if the list of PhoneEntries were sorted into alphabetical order according to name. In fact, it's really not all that hard to keep the list of entries in sorted order, as you'll see in the next subsection.

I will mention that association lists are also called "maps," and Java has a standard parameterized type named Map that implements association lists for keys and values of any type. The implementation is much more efficient than anything you can do with basic arrays. You will encounter this class in Chapter 10.

We've seen that there are good reasons for sorting arrays. There are many algorithms available for doing so. One of the easiest to understand is the insertion sort algorithm. This technique is also applicable to the problem of keeping a list in sorted order as you add new items to the list. Let's consider that case first:

Suppose you have a sorted list and you want to add an item to that list. If you want to make sure that the modified list is still sorted, then the item must be inserted into the right location, with all the smaller items coming before it and all the bigger items after it. This will mean moving each of the bigger items up one space to make room for the new item.

Conceptually, this could be extended to a sorting method if we were to take all the items out of an unsorted array, and then insert them back into the array one-by-one, keeping the list in sorted order as we do so. Each insertion can be done using the insert routine given above. In the actual algorithm, we don't really take all the items from the array; we just remember what part of the array has been sorted:

Here is an illustration of one stage in insertion sort. It shows what happens during one execution of the for loop in the above method, when itemsSorted is 5:

Another typical sorting method uses the idea of finding the biggest item in the list and moving it to the end—which is where it belongs if the list is to be in increasing order. Once the biggest item is in its correct location, you can then apply the same idea to the remaining items. That is, find the next-biggest item, and move it into the next-to-last space, and so forth. This algorithm is called selection sort. It's easy to write:

A variation of selection sort is used in the Hand class that was introduced in Subsection 5.4.1. (By the way, you are finally in a position to fully understand the source code for the Hand class from that section; note that it uses ArrayList. The source file is Hand.java.)

In the Hand class, a hand of playing cards is represented by an ArrayList<Card>. The objects stored in the list are of type Card. A Card object contains instance methods getSuit() and getValue() that can be used to determine the suit and value of the card. In my sorting method, I actually create a new list and move the cards one-by-one from the old list to the new list. The cards are selected from the old list in increasing order. In the end, the new list becomes the hand and the old list is discarded. This is not the most efficient procedure. But hands of cards are so small that the inefficiency is negligible. Here is the code for sorting cards by suit:

This example illustrates the fact that comparing items in a list is not usually as simple as using the operator "<". In this case, we consider one card to be less than another if the suit of the first card is less than the suit of the second, and also if the suits are the same and the value of the second card is less than the value of the first. The second part of this test ensures that cards with the same suit will end up sorted by value.

Sorting a list of Strings raises a similar problem: the "<" operator is not defined for strings. However, the String class does define a compareTo method. If str1 and str2 are of type String, then

returns an int that is 0 when str1 is equal to str2, is less than 0 when str1 precedes str2, and is greater than 0 when str1 follows str2. For example, you can test whether str1 precedes or is equal to str2 by testing

The definition of "precedes" and "follows" for strings uses what is called lexicographic ordering, which is based on the Unicode values of the characters in the strings. Lexicographic ordering is not the same as alphabetical ordering, even for strings that consist entirely of letters (because in lexicographic ordering, all the upper case letters come before all the lower case letters). However, for words consisting strictly of the 26 lower case letters in the English alphabet, lexicographic and alphabetic ordering are the same. (The same holds true if the strings consist entirely of uppercase letters.) The method str1.compareToIgnoreCase(str2) compares the two strings after converting any characters that they contain to lower case.

Insertion sort and selection sort are suitable for sorting fairly small arrays (up to a few hundred elements, say). There are more complicated sorting algorithms that are much faster than insertion sort and selection sort for large arrays, to the same degree that binary search is faster than linear search. The standard method Arrays.sort uses these fast sorting algorithms. I'll discuss one such algorithm in Chapter 9.

I can't resist ending this section on sorting with a related problem that is much less common, but is a bit more fun. That is the problem of putting the elements of an array into a random order. The typical case of this problem is shuffling a deck of cards. A good algorithm for shuffling is similar to selection sort, except that instead of moving the biggest item to the end of the list, an item is selected at random and moved to the end of the list. Here is a subroutine to shuffle an array of ints:

Page 3

Two-dimensional arrays were introduced in Subsection 3.8.5, but we haven't done much with them since then. A 2D array has a type such as int[][] or String[][], with two pairs of square brackets. The elements of a 2D array are arranged in rows and columns, and the new operator for 2D arrays specifies both the number of rows and the number of columns. For example,

This creates a 2D array of int that has 12 elements arranged in 3 rows and 4 columns. Although I haven't mentioned it, there are initializers for 2D arrays. For example, this statement creates the 3-by-4 array that is shown in the picture below:

An array initializer for a 2D array contains the rows of A, separated by commas and enclosed between braces. Each row, in turn, is a list of values separated by commas and enclosed between braces. There are also 2D array literals with a similar syntax that can be used anywhere, not just in declarations. For example,

All of this extends naturally to three-dimensional, four-dimensional, and even higher-dimensional arrays, but they are not used very often in practice.

But before we go any farther, there is a little surprise. Java does not actually have two-dimensional arrays. In a true 2D array, all the elements of the array occupy a continuous block of memory, but that's not true in Java. The syntax for array types is a clue: For any type BaseType, we should be able to form the type BaseType[], meaning "array of BaseType." If we use int[] as the base type, the type that we get is "int[][] meaning "array of int[]" or "array of array of int." And in fact, that's what happens. The elements in a 2D array of type int[][] are variables of type int[]. And remember that a variable of type int[] can only hold a pointer to an array of int. So, a 2D array is really an array of pointers, where each pointer can refer to a one-dimensional array. Those one-dimensional arrays are the rows of the 2D array. A picture will help to explain this. Consider the 3-by-4 array A defined above.

For the most part, you can ignore the reality and keep the picture of a grid in mind. Sometimes, though, you will need to remember that each row in the grid is really an array in itself. These arrays can be referred to as A[0], A[1], and A[2]. Each row is in fact a value of type int[]. It could, for example, be passed to a subroutine that asks for a parameter of type int[].

Some of the consequences of this structure are a little subtle. For example, thinking of a 2D array, A, as an array of arrays, we see that A.length makes sense and is equal to the number of rows of A. If A has the usual shape for a 2D array, then the number of columns in A would be the same as the number of elements in the first row, that is, A[0].length. But there is no rule that says that all of the rows of A must have the same length (although an array created with new BaseType[rows][columns] will always have that form). Each row in a 2D array is a separate one-dimensional array, and each of those arrays can have a different length. In fact, it's even possible for a row to be null. For example, the statement

with no number in the second set of brackets, creates an array of 3 elements where all the elements are null. There are places for three rows, but no actual rows have been created. You can then create the rows A[0], A[1], and A[2] individually.

As an example, consider a symmetric matrix. A symmetric matrix, M, is a two-dimensional array in which the number of rows is equal to the number of columns and satisfying M[i][j] equals M[j][i] for all i and j. Because of this equality, we only really need to store M[i][j] for i >= j. We can store the data in a "triangular matrix":

It's easy enough to make a triangular array, if we create each row separately. To create a 7-by-7 triangular array of double, we can use the code segment

We just have to remember that if we want to know the value of the matrix at (i,j), and if i < j, then we actually have to get the value of matrix[j][i] in the triangular matrix. And similarly for setting values. It's easy to write a class to represent symmetric matrices:

This class is in the file SymmetricMatrix.java, and a small program to test it can be found in TestSymmetricMatrix.java.

By the way, the standard function Arrays.copyOf() can't make a full copy of a 2D array in a single step. To do that, you need to copy each row separately. To make a copy of a two-dimensional array of int, for example:

As an example of more typical 2D array processing, let's look at a very well-known example: John Conway's Game of Life, invented by mathematician John Horton Conway in 1970. This Game of Life is not really a game (although sometimes it's referred to as a "zero-person game" that plays itself). It's a "two-dimensional cellular automaton." This just means that it's a grid of cells whose content changes over time according to definite, deterministic rules. In Life, a cell can only have two possible contents: It can be "alive" or "dead." We will use a 2D array to represent the grid, with each element of the array representing the content of one cell in the grid. In the game, an initial grid is set up in which each cell is marked as either alive or dead. After that, the game "plays itself." The grid evolves through a series of time steps. The contents of the grid at each time step are completely determined by the contents at the previous time step, according to simple rules: Each cell in the grid looks at its eight neighbors (horizontal, vertical, and diagonal) and counts how many of its neighbors are alive. Then the state of the cell in the next step is determined by the rules:

• If the cell is alive in the current time step: If the cell has 2 or 3 living neighbors, then the cell remains alive in the next time step; otherwise, it dies. (A living cell dies of loneliness if it has 0 or 1 living neighbor, and of overcrowding if it has more than 3 living neighbors.)
• If the cell is dead in the current time step: If the cell has 3 living neighbors, then the cell becomes alive in the next time step; otherwise, it remains dead. (Three living cells give birth to a new living cell.)

Here's a picture of part of a Life board, showing the same board before and after the rules have been applied. The rules are applied to every cell in the grid. The picture shows how they apply to four of the cells:

The Game of Life is interesting because it gives rise to many interesting and surprising patterns. (Look it up on Wikipedia.) Here, we are just interested in writing a program to simulate the game. The complete program can be found in the file Life.java. In the program, the life grid is shown as a grid of squares in which dead squares are black and living squares are white. (The program uses MosaicCanvas.java from Section 4.7 to represent the grid, so you will also need that file to compile and run the program.) In the program, you can fill the life board randomly with dead and alive cells, or you can use the mouse to set up the game board. There is a "Step" button that will compute one time-step of the game, and a "Start" button that will run time steps as an animation.

We'll look at some of the array processing involved in implementing the Game of Life for this program. Since a cell can only be alive or dead, it is natural to use a two-dimensional array of boolean[][] to represent the states of all the cells. The array is named alive, and alive[r][c] is true when the cell in row r, column c is alive. The number of rows and the number of columns are equal and are given by a constant, GRID_SIZE. So, for example, to fill the Life grid with random values, the program uses simple nested for loops:

Note that the expression (Math.random() < 0.25) is a true/false value that can be assigned to a boolean array element. The array is also used to set the color of the cells on the screen. Since the grid of cells is displayed on screen as a MosaicCanvas, setting the colors is done using the MosaicCanvas API. Note that the actual drawing is done in the MosaicCanvas class (which has its own 2D array of type Color[][] to keep track of the colors of each cell). The Life program just has to set the colors in the mosaic, using the MosaicCanvas API. This is done in the program in a method named showBoard() that is called each time the board changes. Again, simple nested for loops are used to set the color of each square in the grid:

Of course, the most interesting part of the program is computing the new state of the board by applying the rules to the current state. The rules apply to each individual cell, so again we can use nested for loops to work through all the cells on the board, but this time the processing is more complicated. Note first that we can't make changes to the values in the array as we work through it, since we will need to know the old state of a cell when processing its neighboring cells. In fact, the program uses a second array to hold the new board as it is being created. When the new board is finished, it can be substituted for the old board. The algorithm goes like this in pseudocode:

Note that at the end of the process, alive is pointing to a new array. This doesn't matter as long as the contents of the array represent the new state of the game. The old array will be garbage collected. The test for whether newboard[r][c] should be true or false might not be obvious, but it implements the rules correctly. We still need to work on counting the neighbors. Consider the cell in row r and column c. If it's not at an edge of the board, then it's clear where its neighbors are:

The row above row number r is row number r-1, and the row below is r+1. Similarly for the columns. We just have to look at the values of alive[r-1][c-1], alive[r-1][c], alive[r-1][c+1], alive[r][c-1], alive[r][c+1], alive[r+1][c-1], alive[r+1][c], and alive[r+1][c+1], and count the number that are true. (You should make sure that you understand how the array indexing works here.)

But there is a problem when the cell is along one of the edges of the grid. In that case, some of the array elements in the list don't exist, and an attempt to use them will cause an exception. To avoid the exception, we have to give special consideration to cells along the edges. One idea is that before referencing any array element, check that the array element actually exists. In that case, the code for neighbor counting becomes

All the possible exceptions are avoided. But in my program, I actually do something that is common in 2D computer games—I pretend that the left edge of the board is attached to the right edge and the top edge to the bottom edge. For example, for a cell in row 0, we say that the row "above" is actually the bottom row, row number GRID_SIZE-1. I use variables to represent the positions above, below, left, and right of a given cell. The code turns out to be simpler than the code shown above. Here is the complete method for computing the new board:

Again, I urge you to check out the source code, Life.java, and try the program. Don't forget that you will also need MosaicCanvas.java.

As a final example for this chapter, we'll look at a more substantial example of using a 2D array. This is the longest program that we have encountered so far, with 745 lines of code. The program lets two users play checkers against each other. The checkers game is played on an eight-by-eight board, which is based on an example from Subsection 6.5.1. The players are called "red" and "black," after the color of their checkers. I'm not going to explain the rules of checkers here; possibly you can learn them by trying out the program.

In the program, a player moves by clicking on the piece that they want to move, and then clicking on the empty square to which it is to be moved. As an aid to the players, any square that the current player can legally click at a given time is highlighted with a brightly colored border. The square containing a piece that has been selected to be moved, if any, is surrounded by a yellow border. Other pieces that can legally be moved are surrounded by a cyan-colored border. If a piece has already been selected to be moved, each empty square that it can legally move to is highlighted with a green border. The game enforces the rule that if the current player can jump one of the opponent's pieces, then the player must jump. When a player's piece becomes a king, by reaching the opposite end of the board, a big white "K" is drawn on the piece. Here is a picture of the program early in a game. It is black's turn to move. Black has selected the piece in the yellow-outlined square to be moved. Black can click one of the squares outlined in green to complete the move, or can click one of the squares outlined in cyan to select a different piece to be moved.

I will only cover a part of the programming for this example. I encourage you to read the complete source code, Checkers.java. It's long and complex, but with some study, you should understand all the techniques that it uses. The program is a good example of state-based, event-driven, object-oriented programming.

The data about the pieces on the board are stored in a two-dimensional array. Because of the complexity of the program, I wanted to divide it into several classes. In addition to the main class, there are several nested classes. One of these classes is CheckersData, which handles the data for the board. It is not directly responsible for any part of the graphics or event-handling, but it provides methods that can be called by other classes that handle graphics and events. It is mainly this class that I want to talk about.

The CheckersData class has an instance variable named board of type int[][]. The value of board is set to "new int[8][8]", an 8-by-8 grid of integers. The values stored in the grid are defined as constants representing the possible contents of a square on a checkerboard:

The constants RED and BLACK are also used in my program (or, perhaps, misused) to represent the two players in the game. When a game is started, the values in the array are set to represent the initial state of the board. The grid of values looks like

A regular black piece can only move "down" the grid. That is, the row number of the square it moves to must be greater than the row number of the square it comes from. A regular red piece can only move up the grid. Kings of either color can move in both directions.

One function of the CheckersData class is to take care of changes to the data structures that need to be made when one of the users moves a checker. An instance method named makeMove() is provided to do this. When a player moves a piece from one square to another, the values of two elements in the array are changed. But that's not all. If the move is a jump, then the piece that was jumped is removed from the board. (The method checks whether the move is a jump by checking if the square to which the piece is moving is two rows away from the square where it starts.) Furthermore, a RED piece that moves to row 0 or a BLACK piece that moves to row 7 becomes a king. Putting all that into a subroutine is good programming: the rest of the program doesn't have to worry about any of these details. It just calls this makeMove() method:

An even more important function of the CheckersData class is to find legal moves on the board. In my program, a move in a Checkers game is represented by an object belonging to the following class:

The CheckersData class has an instance method which finds all the legal moves that are currently available for a specified player. This method is a function that returns an array of type CheckersMove[]. The array contains all the legal moves, represented as CheckersMove objects. The specification for this method reads

A brief pseudocode algorithm for the method is

Now, what is this "list"? We have to return the legal moves in an array. But since an array has a fixed size, we can't create the array until we know how many moves there are, and we don't know that until near the end of the method, after we've already made the list! A neat solution is to use an ArrayList instead of an array to hold the moves as we find them. In fact, I use an object defined by the parameterized type ArrayList<CheckersMove> so that the list is restricted to holding objects of type CheckersMove. As we add moves to the list, it will grow just as large as necessary. At the end of the method, we can create the array that we really want and copy the data into it:

Now, how do we find the legal jumps or the legal moves? The information we need is in the board array, but it takes some work to extract it. We have to look through all the positions in the array and find the pieces that belong to the current player. For each piece, we have to check each square that it could conceivably move to, and check whether that would be a legal move. If we are looking for legal jumps, we want to look at squares that are two rows and two columns away from the piece. There are four squares to consider. Thus, the line in the algorithm that says "Find any legal jumps and add them to moves" expands to:

The line that says "Find any other legal moves and add them to moves" expands to something similar, except that we have to look at the four squares that are one column and one row away from the piece. Testing whether a player can legally move from one given square to another given square is itself non-trivial. The square the player is moving to must actually be on the board, and it must be empty. Furthermore, regular red and black pieces can only move in one direction. I wrote the following utility method to check whether a player can make a given non-jump move:

This method is called by my getLegalMoves() method to check whether one of the possible moves that it has found is actually legal. I have a similar method that is called to check whether a jump is legal. In this case, I pass to the method the square containing the player's piece, the square that the player might move to, and the square between those two, which the player would be jumping over. The square that is being jumped must contain one of the opponent's pieces. This method has the specification:

Given all this, you should be in a position to understand the complete getLegalMoves() method. It's a nice way to finish off this chapter, since it combines several topics that we've looked at: one-dimensional arrays, ArrayLists, and two-dimensional arrays:

The checkers program is complex, and you can be sure that it didn't just fall together. It took a good deal of design work to decide what classes and objects would be used, what methods should be written, and what algorithms the methods should use. The complete source code is in the file Checkers.java. Take a look!

End of Chapter 7