7.3.

DYNAMIC ARRAYS AND ARRAYLISTS 335

[Link]("? ");
num = [Link]();
if (num <= 0)
break;
[Link](numCount, num); // Store num in the dynamic array.
numCount++;
}

[Link]("\nYour numbers in reverse order are:\n");

for (int i = numCount - 1; i >= 0; i--) {

[Link]( [Link](i) ); // Print the i-th number.
}

} // end main();

} // end class ReverseWithDynamicArray

7.3.3 ArrrayLists
The DynamicArrayOfInt class could be used in any situation where an array of int with no preset
limit on the size is needed. However, if we want to store Shapes instead of ints, we would have
to dene a new class to do it. That class, probably named “DynamicArrayOfShape”, would look
exactly the same as the DynamicArrayOfInt class except that everywhere the type “int” appears,
it would be replaced by the type “Shape”. Similarly, we could dene a DynamicArrayOfDouble
class, a DynamicArrayOfPlayer class, and so on. But there is something a little silly about this,
since all these classes are close to being identical. It would be nice to be able to write some
kind of source code, once and for all, that could be used to generate any of these classes on
demand, given the type of value that we want to store. This would be an example of generic
programming . Some programming languages, including C++, have had support for generic
programming for some time. With version 5.0, Java introduced true generic programming,
but even before that it had something that was very similar: One can come close to generic
programming in Java by working with data structures that contain elements of type Object.
We will rst consider the almost-generic programming that has been available in Java from
the beginning, and then we will look at the change that was introduced in Java 5.0. A full
discussion of generic programming will be given in Chapter 10.
In Java, every class is a subclass of the class named Object. This means that every object can
be assigned to a variable of type Object. Any object can be put into an array of type Object[ ].
If we dened a DynamicArrayOfObject class, then we could store objects of any type. This is not
true generic programming, and it doesn’t apply to the primitive types such as int and double.
But it does come close. In fact, there is no need for us to dene a DynamicArrayOfObject class.
Java already has a standard class named ArrayList that serves much the same purpose. The
ArrayList class is in the package [Link], so if you want to use it in a program, you should
put the directive “import [Link];” at the beginning of your source code le.
The ArrayList class diers from my DynamicArrayOfInt class in that an ArrayList object
always has a denite size, and it is illegal to refer to a position in the ArrayList that lies outside
its size. In this, an ArrayList is more like a regular array. However, the size of an ArrayList can
be increased at will. The ArrayList class denes many instance methods. I’ll describe some of
the most useful. Suppose that list is a variable of type ArrayList. Then we have:
336 CHAPTER 7. ARRAYS

• [Link]() — This function returns the current size of the ArrayList. The only valid
positions in the list are numbers in the range 0 to [Link]()-1. Note that the size can
be zero. A call to the default constructor new ArrayList() creates an ArrayList of size
zero.
• [Link](obj) — Adds an object onto the end of the list, increasing the size by 1. The
parameter, obj, can refer to an object of any type, or it can be null.
• [Link](N) — This function returns the value stored at position N in the ArrayList. N
must be an integer in the range 0 to [Link]()-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 [Link](N) on the left side of an
assignment statement.
• [Link](N, obj) — Assigns the object, obj, to position N in the ArrayList, replacing
the item previously stored at position N. The integer N must be in the range from 0 to
[Link]()-1. A call to this function is equivalent to the command A[N] = obj for an
array A.
• [Link](obj) — If the specied object occurs somewhere in the ArrayList, it is
removed from the list. Any items in the list that come after the removed item are moved
down one position. The size of the ArrayList decreases by 1. If obj occurs more than once
in the list, only the rst copy is removed.
• [Link](N) — For an integer, N, this removes the N-th item in the ArrayList. N must
be in the range 0 to [Link]()-1. Any items in the list that come after the removed
item are moved down one position. The size of the ArrayList decreases by 1.
• [Link](obj) — A function that searches for the object, obj, in the ArrayList. If
the object is found in the list, then the position number where it is found is returned. If
the object is not found, then -1 is returned.
For example, suppose again that players in a game are represented by objects of type Player.
The players currently in the game could be stored in an ArrayList named players. This variable
would be declared as
ArrayList players;
and initialized to refer to a new, empty ArrayList object with
players = new ArrayList();
If newPlayer is a variable that refers to a Player object, the new player would be added to the
ArrayList and to the game by saying
[Link](newPlayer);
and if player number i leaves the game, it is only necessary to say
[Link](i);
Or, if player is a variable that refers to the Player that is to be removed, you could say
[Link](player);
All this works very nicely. The only slight diculty arises when you use the function
[Link](i) to get the value stored at position i in the ArrayList. The return type of
this function is Object. In this case the object that is returned by the function is actually of
type Player. In order to do anything useful with the returned value, it’s usually necessary to
type-cast it to type Player :
7.3. DYNAMIC ARRAYS AND ARRAYLISTS 337

Player plr = (Player)[Link](i);

For example, if the Player class includes an instance method makeMove() that is called to allow
a player to make a move in the game, then the code for letting every player make a move is
for (int i = 0; i < [Link](); i++) {
Player plr = (Player)[Link](i);
[Link]();
}
The two lines inside the for loop can be combined to a single line:
((Player)[Link](i)).makeMove();
This gets an item from the list, type-casts it, and then calls the makeMove() method on the
resulting Player. The parentheses around “(Player)[Link](i)” are required because
of Java’s precedence rules. The parentheses force the type-cast to be performed before the
makeMove() method is called.
For-each loops work for ArrayLists just as they do for arrays. But note that since the items
in an ArrayList are only known to be Objects, the type of the loop control variable must be
Object. For example, the for loop used above to let each Player make a move could be written
as the for-each loop
for ( Object plrObj : players ) {
Player plr = (Player)plrObj;
[Link]();
}
In the body of the loop, the value of the loop control variable, plrObj, is one of the objects
from the list, players. This object must be type-cast to type Player before it can be used.
∗ ∗ ∗
In Subsection 5.5.5, I discussed a program, ShapeDraw, that uses ArrayLists. Here is another
version of the same idea, simplied to make it easier to see how ArrayList is being used. The
program supports the following operations: Click the large white drawing area to add a colored
rectangle. (The color of the rectangle is given by a “rainbow palette” along the bottom of the
applet; click the palette to select a new color.) Drag rectangles using the right mouse button.
Hold down the Alt key and click on a rectangle to delete it. Shift-click a rectangle to move it
out in front of all the other rectangles. You can try an applet version of the program in the
on-line version of this section.
Source code for the main panel for this program can be found in [Link].
You should be able to follow the source code in its entirety. (You can also take a look at the
le [Link], which denes the color palette shown at the bottom of the applet, if
you like.) Here, I just want to look at the parts of the program that use an ArrayList.
The applet uses a variable named rects, of type ArrayList, to hold information about the
rectangles that have been added to the drawing area. The objects that are stored in the list
belong to a static nested class, ColoredRect, that is dened as
/**
* An object of type ColoredRect holds the data for one colored rectangle.
*/
private static class ColoredRect {
int x,y; // Upper left corner of the rectangle.
int width,height; // Size of the rectangle.
Color color; // Color of the rectangle.
}
338 CHAPTER 7. ARRAYS

If g is a variable of type Graphics, then the following code draws all the rectangles that
are stored in the list rects (with a black outline around each rectangle):
for (int i = 0; i < [Link](); i++) {
ColoredRect rect = (ColoredRect)[Link](i);
[Link]( [Link] );
[Link]( rect.x, rect.y, [Link], [Link]);
[Link]( [Link] );
[Link]( rect.x, rect.y, [Link] - 1, [Link] - 1);
}

The i-th rectangle in the list is obtained by calling [Link](i). Since this method returns
a value of type Object, the return value must be typecast to its actual type, ColoredRect, to get
access to the data that it contains.
To implement the mouse operations, it must be possible to nd the rectangle, if any, that
contains the point where the user clicked the mouse. To do this, I wrote the function
/**
* Find the topmost rect that contains the point (x,y). Return null
* if no rect contains that point. The rects in the ArrayList are
* considered in reverse order so that if one lies on top of another,
* the one on top is seen first and is returned.
*/
ColoredRect findRect(int x, int y) {
for (int i = [Link]() - 1; i >= 0; i--) {
ColoredRect rect = (ColoredRect)[Link](i);
if ( x >= rect.x && x < rect.x + [Link]
&& y >= rect.y && y < rect.y + [Link] )
return rect; // (x,y) is inside this rect.
}
return null; // No rect containing (x,y) was found.
}

The code for removing a ColoredRect, rect, from the drawing area is simply
[Link](rect) (followed by a repaint()). Bringing a given rectangle out in front of
all the other rectangles is just a little harder. Since the rectangles are drawn in the order in
which they occur in the ArrayList, the rectangle that is in the last position in the list is in front
of all the other rectangles on the screen. So we need to move the selected rectangle to the
last position in the list. This can most easily be done in a slightly tricky way using built-in
ArrayList operations: The rectangle is simply removed from its current position in the list and
then adding back at the end of the list:
void bringToFront(ColoredRect rect) {
if (rect != null) {
[Link](rect); // Remove rect from the list.
[Link](rect); // Add it back; it will be placed in the last position.
repaint();
}
}

This should be enough to give you the basic idea. You can look in the source code for more
details.
7.3. DYNAMIC ARRAYS AND ARRAYLISTS 339

7.3.4 Parameterized Types

The main dierence between true generic programming and the ArrayList examples in the
previous subsection is the use of the type Object as the basic type for objects that are stored
in a list. This has at least two unfortunate consequences: First, it makes it necessary to use
type-casting in almost every case when an element is retrieved from that list. Second, since
any type of object can legally be added to the list, there is no way for the compiler to detect
an attempt to add the wrong type of object to the list; the error will be detected only at run
time when the object is retrieved from the list and the attempt to type-cast the object fails.
Compare this to arrays. An array of type BaseType[ ] can only hold objects of type BaseType.
An attempt to store an object of the wrong type in the array will be detected by the compiler,
and there is no need to type-cast items that are retrieved from the array back to type BaseType.
To address this problem, Java 5.0 introduced parameterized types. ArrayList is an ex-
ample: Instead of using the plain “ArrayList” type, it is possible to use ArrayList<BaseType>,
where BaseType is any object type, that is, the name of a class or of an interface. (BaseType
cannot be one of the primitive types.) ArrayList<BaseType> can be used to create lists that
can hold only objects of type BaseType. For example,
ArrayList<ColoredRect> rects;

declares a variable named rects of type ArrayList<ColoredRect>, and

rects = new ArrayList<ColoredRect>();

sets rects to refer to a newly created list that can only hold objects belonging to the class
ColoredRect (or to a subclass). The funny-looking name “ArrayList<ColoredRect>” is being
used here in exactly the same way as an ordinary class name—don’t let the “<ColoredRect>”
confuse you; it’s just part of the name of the type. When a statement such as [Link](x);
occurs in the program, the compiler can check whether x is in fact of type ColoredRect. If not,
the compiler will report a syntax error. When an object is retrieve from the list, the compiler
knows that the object must be of type ColoredRect, so no type-cast is necessary. You can say
simply:
ColoredRect rect = [Link](i)

You can even refer directly to an instance variable in the object, such as [Link](i).color.
This makes using ArrayList<ColoredRect> very similar to using ColoredRect[ ] with the added
advantage that the list can grow to any size. Note that if a for-each loop is used to process the
items in rects, the type of the loop control variable can be ColoredRect, and no type-cast is
necessary. For example, when using ArrayList<ColoredRect> as the type for the list rects, the
code for drawing all the rectangles in the list could be rewritten as:
for ( ColoredRect rect : rects ) {
[Link]( [Link] );
[Link]( rect.x, rect.y, [Link], [Link]);
[Link]( [Link] );
[Link]( rect.x, rect.y, [Link] - 1, [Link] - 1);
}

You can use ArrayList<ColoredRect> anyplace where you could use a normal type: to declare
variables, as the type of a formal parameter in a subroutine, or as the return type of a subroutine.
You can even create a subclass of ArrayList<ColoredRect>! (Nevertheless, technically speaking,
ArrayList<ColoredRect> is not considered to be a separate class from ArrayList. An object of
340 CHAPTER 7. ARRAYS

type ArrayList<ColoredRect> actually belongs to the class ArrayList, but the compiler restricts
the type of objects that can be added to the list.)
The only drawback to using parameterized types is that the base type cannot be a primitive
type. For example, there is no such thing as “ArrayList<int>”. However, this is not such a
big drawback as it might seem at rst, because of the “wrapper types” and “autoboxing” that
were introduced in Subsection 5.3.2. A wrapper type such as Double or Integer can be used as
a base type for a parameterized type. An object of type ArrayList<Double> can hold objects of
type Double. Since each object of type Double holds a value of type double, it’s almost like
having a list of doubles. If numlist is declared to be of type ArrayList<Double> and if x is of
type double, then the value of x can be added to the list by saying:
[Link]( new Double(x) );

Furthermore, because of autoboxing, the compiler will automatically do double-to-Double and

Double-to-double type conversions when necessary. This means that the compiler will treat
“[Link](x)” as begin equivalent to “[Link]( new Double(x) )”. So, behind the
scenes, “[Link](x)” is actually adding an object to the list, but it looks a lot as if you
are working with a list of doubles.
∗ ∗ ∗
The sample program [Link] demonstrates the use of parameterized types. In
this program, the user can sketch curves in a drawing area by clicking and dragging with the
mouse. The curves can be of any color, and 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” command that turns a symmetry feature on and o. Curves that are
drawn by the user when the symmetry option is on are reected horizontally and vertically
to produce a symmetric pattern. You can try an applet version of the program in the on-line
version of this section.
Unlike the original SimplePaint program in Subsection 6.4.4, this new version uses a data
structure to store information about the picture that has been drawn by the user. This data
is used in the paintComponent() method to redraw the picture whenever necessary. Thus, the
picture doesn’t disappear when, for example, the picture is covered and then uncovered. The
data structure is implemented using ArrayLists.
The main data for a curve consists of a list of the points on the curve. This data can be stored
in an object of type ArrayList<Point>, where [Link] is one of Java’s standard classes.
(A Point object contains two public integer variables x and y that represent the coordinates of
a point.) However, 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 can be grouped into an object of type CurveData that is dened as
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, we can use
a variable curves declared as
7.3. DYNAMIC ARRAYS AND ARRAYLISTS 341

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 and added to the list of curves. The instance variables in the new CurveData object
must also be initialized. Here is the code from the mousePressed() routine that does this:
currentCurve = new CurveData(); // Create a new CurveData object.
[Link] = currentColor; // The color of the curve is taken from an
// instance variable that represents the
// currently selected drawing color.
[Link] = useSymmetry; // The "symmetric" property of the curve
// is also copied from the current value
// of an instance variable, useSymmetry.
[Link] = new ArrayList<Point>(); // Create a new point list object.
[Link]( new Point([Link](), [Link]()) );
// The point where the user pressed the mouse is the first point on
// the curve. A new Point object is created to hold the coordinates
// of that point and is added to the list of points for the curve.
[Link](currentCurve); // Add the CurveData object to the list of curves.

As the user drags the mouse, new points are added to currentCurve, and repaint() is called.
When the picture is redrawn, the new point will be part of the picture.
The paintComponent() method has to use 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:
for ( CurveData curve : curves ) {
.
. // Draw the curve represented by the object, curve, of type CurveData.
.
}

In the body of this loop, [Link] 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: [Link](i). This returns a value of type Point which contains
instance variables named x and y. We can refer directly to the x-coordinate of the i-th point
as:
[Link](i).x

This might seem rather complicated, but it’s a nice example of a complex name that species
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 instance variable named x. Here is the
complete denition of the paintCompontent() method:
public void paintComponent(Graphics g) {
[Link](g);
for ( CurveData curve : curves) {
[Link]([Link]);
for (int i = 1; i < [Link](); i++) {
342 CHAPTER 7. ARRAYS

// Draw a line segment from point number i-1 to point number i.

int x1 = [Link](i-1).x;
int y1 = [Link](i-1).y;
int x2 = [Link](i).x;
int y2 = [Link](i).y;
[Link](x1,y1,x2,y2);
if ([Link]) {
// Also draw the horizontal and vertical reflections
// of the line segment.
int w = getWidth();
int h = getHeight();
[Link](w-x1,y1,w-x2,y2);
[Link](x1,h-y1,x2,h-y2);
[Link](w-x1,h-y1,w-x2,h-y2);
}
}
}
} // end paintComponent()
I encourage you to read the full source code, [Link]. In addition to serving as
an example of using parameterized types, it also serves an another example of creating and
using menus.

7.3.5 Vectors
The ArrayList class was introduced in Java version 1.2, as one of a group of classes designed
for working with collections of objects. We’ll look at these “collection classes” in Chapter 10.
Early versions of Java did not include ArrayList, but they did have a very similar class named
[Link]. You can still see Vectors used in older code and in many of Java’s standard
classes, so it’s worth knowing about them. Using a Vector is similar to using an ArrayList, except
that dierent names are used for some commonly used instance methods, and some instance
methods in one class don’t correspond to any instance method in the other class.
Like an ArrayList, a Vector is similar to an array of Objects that can grow to be as large as
necessary. The default constructor, new Vector(), creates a vector with no elements. Suppose
that vec is a Vector. Then we have:
• [Link]() — a function that returns the number of elements currently in the vector.
• [Link](N) — returns the N-th element of the vector, for an integer N. N must be
in the range 0 to [Link]()-1. This is the same as get(N) for an ArrayList.
• [Link](obj,N) — sets the N-th element in the vector to be obj. N must be
in the range 0 to [Link]()-1. This is the same as set(N,obj) for an ArrayList.
• [Link](obj) — adds the Object, obj, to the end of the vector. This is the same
as the add() method of an ArrayList.
• [Link](obj) — removes obj from the vector, if it occurs. Only the rst
occurrence is removed. This is the same as remove(obj) for an ArrayList.
• [Link](N) — removes the N-th element, for an integer N. N must be in
the range 0 to [Link]()-1. This is the same as remove(N) for an ArrayList.
• [Link](N) — sets the size of the vector to N. If there were more than N elements in
vec, the extra elements are removed. If there were fewer than N elements, extra spaces are
lled with null. The ArrayList class, unfortunately, does not have a setSize() method.
7.4. SEARCHING AND SORTING 343

The Vector class includes many more methods, but these are probably the most commonly
used. Note that in Java 5.0, Vector can be used as a paramaterized type in exactly the same
way as ArrayList. That is, if BaseType is any class or interface name, then Vector<BaseType>
represents vectors that can hold only objects of type BaseType.

7.4 Searching and Sorting

Two array processing techniques that are particularly common are searching and sort-
ing . Searching here refers to nding an item in the array that meets some specied 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).
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 nd
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 that array. 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 elds of
the record. In the mailing list example, each record would contain a name and address. The
elds of the record might be the rst name, last name, street address, state, city and zip code.
For the purpose of searching or sorting, one of the elds is designated to be the key eld.
Searching then means nding a record in the array that has a specied value in its key eld.
Sorting means moving the records around in the array so that the key elds 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.

7.4.1 Searching
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 nished. If you look at every item without nding 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 specied 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:
/**
344 CHAPTER 7. ARRAYS

* Searches the array A for the integer N. If N is not in the array,

* then -1 is returned. If N is in the array, then return value is
* the first integer i that satisfies A[i] == N.
*/
static int find(int[] A, int N) {
for (int index = 0; index < [Link]; index++) {
if ( A[index] == N )
return index; // N has been found at this index!
}
// If we get this far, then N has not been found
// anywhere in the array. Return a value of -1.
return -1;
}

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 decreas-
ing 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 o.
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 nd 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 rst half of the range can
be eliminated. If the number in the middle just happens to be N exactly, then the search is
nished. If the size of the range decreases to zero, then the number N does not occur in the
array. Here is a subroutine that returns the location of N in a sorted array A. If N cannot be
found in the array, then a value of -1 is returned instead:
/**