Section 8.3
Dynamic Arrays, ArrayLists, and Vectors
THE SIZE OF AN ARRAY is fixed when it is created. In many cases, however, the number of data items that are actually stored in the array varies with time. Consider the following examples: An array that stores the lines of text in a word-processing program. An array that holds the list of computers that are currently downloading a page from a Web site. An array that contains the shapes that have been added to the screen by the user of a drawing program. Clearly, we need some way to deal with cases where the number of data items in an array is not fixed.
Partially Full Arrays
Consider an application where the number of items that we want to store in an array changes as the program runs. Since the size of the array can't actually be changed, a separate counter variable must be used to keep track of how many spaces in the array are in use. (Of course, every space in the array has to contain something; the question is, how many spaces contain useful or valid items?)
Consider, for example, a program that reads positive integers entered by the user and stores them for later processing. The program stops reading when the user inputs a number that is less than or equal to zero. The input numbers can be kept in an array, numbers, of type int[]. Let's say that no more than 100 numbers will be input. Then the size of the array can be fixed at 100. But the program must keep track of how many numbers have actually been read and stored in the array. For this, it can use an integer variable, numCt. Each time a number is stored in the array, numCt must be incremented by one. As a rather silly example, let's write a program that will read the numbers input by the user and then print them in reverse order. (This is, at least, a processing task that requires that the numbers be saved in an array. Remember that many types of processing, such as finding the sum or average or maximum of the numbers, can be done without saving the individual numbers.)
public class ReverseInputNumbers {
public static void main(String[] args) {
int[] numbers; // An array for storing the input values.
int numCt; // The number of numbers saved in the array.
int num; // One of the numbers input by the user.
numbers = new int[100]; // Space for 100 ints.
numCt = 0; // No numbers have been saved yet.
TextIO.putln("Enter up to 100 positive integers; enter 0 to end.");
while (true) { // Get the numbers and put them in the array.
TextIO.put("? ");
num = TextIO.getlnInt();
if (num <= 0)
break;
numbers[numCt] = num;
numCt++;
}
TextIO.putln("\nYour numbers in reverse order are:\n");
for (int i = numCt - 1; i >= 0; i--) {
TextIO.putln( numbers[i] );
}
} // end main();
} // end class ReverseInputNumbers
It is especially important to note that the variable numCt plays a dual role. It is the number of numbers that have been entered into the array. But it is also the index of the next available spot in the array. For example, if 4 numbers have been stored in the array, they occupy locations number 0, 1, 2, and 3. The next available spot is location 4. When the time comes to print out the numbers in the array, the last occupied spot in the array is location numCt - 1, so the for loop prints out values starting from location numCt - 1 and going down to 0.
Let's look at another, more realistic example. Suppose that you write a game program, and that players can join the game and leave the game as it progresses. As a good object-oriented programmer, you probably have a class named Player to represent the individual players in the game. A list of all players who are currently in the game could be stored in an array, playerList, of type Player[]. Since the number of players can change, you will also need a variable, playerCt, to record the number of players currently in the game. Assuming that there will never be more than 10 players in the game, you could declare the variables as:
Player[] playerList = new Player[10]; // Up to 10 players.
int playerCt = 0; // At the start, there are no players.
After some players have joined the game, playerCt will be greater than 0, and the player objects representing the players will be stored in the array elements playerList[0], playerList[1], ..., playerList[playerCt-1]. Note that the array element playerList[playerCt] is not in use. The procedure for adding a new player, newPlayer, to the game is simple:
playerList[playerCt] = newPlayer; // Put new player in next
// available spot.
playerCt++; // And increment playerCt to count the new player.
Deleting a player from the game is a little harder, since you don't want to leave a "hole" in the array. Suppose you want to delete the player at index k in playerList. If you are not worried about keeping the players in any particular order, then one way to do this is to move the player from the last occupied position in the array into position k and then to decrement the value of playerCt:
playerList[k] = playerList[playerCt - 1];
playerCt--;
The player previously in position k is no longer in the array. The player previously in position playerCt - 1 is now in the array twice. But it's only in the occupied or valid part of the array once, since playerCt has decreased by one. Remember that every element of the array has to hold some value, but only the values in positions 0 through playerCt - 1 will be looked at or processed in any way.
Suppose that when deleting the player in position k, you'd like to keep the remaining players in the same order. (Maybe because they take turns in the order in which they are stored in the array.) To do this, all the players in positions k+1 and above must move down one position in the array. Player k+1 replaces player k, who is out of the game. Player k+2 fills the spot left open when player k+1 moved. And so on. The code for this is
for (int i = k+1; i < playerCt; i++) {
playerList[i-1] = playerList[i];
}
playerCt--;
It's worth emphasizing that the Player example deals with an array whose base type is a class. An item in the array is either null or is a reference to an object belonging to the class, Player. The Player objects themselves are not really stored in the array, only references to them. Note that because of the rules for assignment in Java, the objects can actually belong to subclasses of Player. Thus there could be different classes of Players such as computer players, regular human players, players who are wizards, ..., all represented by different subclasses of Player.
As another example, suppose that a class Shape represents the general idea of a shape drawn on a screen, and that it has subclasses to represent specific types of shapes such as lines, rectangles, rounded rectangles, ovals, filled-in ovals, and so forth. (Shape itself would be an abstract class, as discussed in Section 5.4.) Then an array of type Shape[] can hold references to objects belonging to the subclasses of Shape. For example, the situation created by the statements
Shape[] shapes = new Shape[100]; // Array to hold up to 100 shapes.
shapes[0] = new Rect(); // Put some objects in the array.
shapes[1] = new Line(); // (A real program would
shapes[2] = new FilledOval(); // use some parameters here.)
int shapeCt = 3; // Keep track of number of objects in array.
could be illustrated as:
Such an array would be useful in a drawing program. The array could be used to hold a list of shapes to be displayed. If the Shape class includes a method, "void redraw(Graphics g)" for drawing the shape in a graphics context g, then all the shapes in the array could be redrawn with a simple for loop:
for (int i = 0; i < shapeCt; i++)
shapes[i].redraw(g);
The statement "shapes[i].redraw(g);" calls the redraw() method belonging to the particular shape at index i in the array. Each object knows how to redraw itself, so that repeated executions of the statement can produce a variety of different shapes on the screen. This is nice example both of polymorphism and of array processing.
Dynamic Arrays
In each of the above examples, an arbitrary limit was set on the number of items -- 100 ints, 10 Players, 100 Shapes. Since the size of an array is fixed, a given array can only hold a certain maximum number of items. In many cases, such an arbitrary limit is undesirable. Why should a program work for 100 data values, but not for 101? The obvious alternative of making an array that's so big that it will work in any practical case is not usually a good solution to the problem. It means that in most cases, a lot of computer memory will be wasted on unused space in the array. That memory might be better used for something else. And what if someone is using a computer that could handle as many data values as the user actually wants to process, but doesn't have enough memory to accommodate all the extra space that you've allocated?
Clearly, it would be nice if we could increase the size of an array at will. This is not possible, but what is possible is just as good. Remember that an array variable does not actually hold an array. It just holds a reference to an array object. We can't make the array bigger, but we can make a new, bigger array object and change the value of the array variable so that it refers to the bigger array. Of course, we also have to copy the contents of the old array into the new array. The array variable then refers to an array object that contains all the data of the old array, with room for additional data. The old array will be garbage collected, since it is no longer in use.
Let's look back at the game example, in which playerList is an array of type Player[] and playerCt is the number of spaces that have been used in the array. Suppose that we don't want to put a pre-set limit on the number of players. If a new player joins the game and the current array is full, we just make a new, bigger one. The same variable, playerList, will refer to the new array. Note that after this is done, playerList[0] will refer to a different memory location, but the value stored in playerList[0] will still be the same as it was before. Here is some code that will do this:
// Add a new player, even if the current array is full.
if (playerCt == playerList.length) {
// Array is full. Make a new, bigger array,
// copy the contents of the old array into it,
// and set playerList to refer to the new array.
int newSize = 2 * playerList.length; // Size of new array.
Player[] temp = new Player[newSize]; // The new array.
System.arraycopy(playerList, 0, temp, 0, playerList.length);
playerList = temp; // Set playerList to refer to new array.
}
// At this point, we KNOW there is room in the array.
playerList[playerCt] = newPlayer; // Add the new player...
playerCt++; // ...and count it.
If we are going to be doing things like this regularly, it would be nice to define a reusable class to handle the details. An array-like object that changes size to accommodate the amount of data that it actually contains is called a dynamic array. A dynamic array supports the same operations as an array: putting a value at a given position and getting the value that is stored at a given position. But there is no upper limit on the positions that can be used (except those imposed by the size of the computer's memory). In a dynamic array class, the put and get operations must be implemented as instance methods. Here, for example, is a class that implements a dynamic array of ints:
public class DynamicArrayOfInt {
private int[] data; // An array to hold the data.
public DynamicArrayOfInt() {
// Constructor.
data = new int[1]; // Array will grow as necessary.
}
public int get(int position) {
// Get the value from the specified position in the array.
// Since all array positions are initially zero, when the
// specified position lies outside the actual physical size
// of the data array, a value of 0 is returned.
if (position >= data.length)
return 0;
else
return data[position];
}
public void put(int position, int value) {
// Store the value in the specified position in the array.
// The data array will increase in size to include this
// position, if necessary.
if (position >= data.length) {
// The specified position is outside the actual size of
// the data array. Double the size, or if that still does
// not include the specified position, set the new size
// to 2*position.
int newSize = 2 * data.length;
if (position >= newSize)
newSize = 2 * position;
int[] newData = new int[newSize];
System.arraycopy(data, 0, newData, 0, data.length);
data = newData;
// The following line is for demonstration purposes only.
System.out.println("Size of dynamic array increased to "
+ newSize);
}
data[position] = value;
}
} // end class DynamicArrayOfInt
The data in a DynamicArrayOfInt object is actually stored in a regular array, but that array is discarded and replaced by a bigger array whenever necessary. If numbers is a variable of type DynamicArrayOfInt, then the command numbers.put(pos,val) stores the value val at position number pos in the dynamic array. The function numbers.get(pos) returns the value stored at position number pos.
The first example in this section used an array to store positive integers input by the user. We can rewrite that example to use a DynamicArrayOfInt. A reference to numbers[i] is replaced by numbers.get(i). The statement "numbers[numCt] = num;" is replaced by "numbers.put(numCt,num);". Here's the program:
public class ReverseWithDynamicArray {
public static void main(String[] args) {
DynamicArrayOfInt numbers; // To hold the input numbers.
int numCt; // The number of numbers stored in the array.
int num; // One of the numbers input by the user.
numbers = new DynamicArrayOfInt();
numCt = 0;
TextIO.putln("Enter some positive integers; Enter 0 to end");
while (true) { // Get numbers and put them in the dynamic array.
TextIO.put("? ");
num = TextIO.getlnInt();
if (num <= 0)
break;
numbers.put(numCt, num); // Store num in the dynamic array.
numCt++;
}
TextIO.putln("\nYour numbers in reverse order are:\n");
for (int i = numCt - 1; i >= 0; i--) {
TextIO.putln( numbers.get(i) ); // Print the i-th number.
}
} // end main();
} // end class ReverseWithDynamicArray
The following applet simulates this program. I've included an output statement in the DynamicArrayOfInt class. This statement will inform you each time the data array increases in size. (Of course, the output statement doesn't really belong in the class. It's included here for demonstration purposes.)
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 define 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 define 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, such as C++, have support for generic programming. Java does not, at least not quite. We can come close to generic programming in Java by working with data structures that contain elements of type Object.
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 a subroutine has a formal parameter of type Object, than any object can be passed to the subroutine as an actual parameter. If we defined 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 define a DynamicArrayOfObject class. Java already has a standard class named ArrayList that serves much the same purpose. The ArrayList class is in the package java.util, so if you want to use the ArrayList class in a program, you should put the directive "import java.util.ArrayList;" or "import java.util.*;" at the beginning of your source code file.
The ArrayList class differs from my DynamicArrayOfInt class in that an ArrayList object always has a definite 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 defines many instance methods. I'll describe some of the most useful. Suppose that list is a variable of type ArrayList.
list.size() -- This function returns the current size of the ArrayList. 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() creates an ArrayList of size zero.
list.add(obj) -- Adds an object onto the end of the ArrayList, increasing the size by 1. The parameter, obj, can refer to an object of any type, or it can be null.
list.get(N) -- This function returns the value stored at position N in the ArrayList. N must be an integer in the range 0 to list.size()-1. If N is outside this range, an error 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 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.remove(obj) -- If the specified 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 first copy is removed.
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 down one position. The size of the ArrayList decreases by 1.
list.indexOf(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
players.add(newPlayer);
and if player number i leaves the game, it is only necessary to say
players.remove(i);
Or, if player is a variable that refers to the Player that is to be removed, you could say
players.remove(player);
All this works very nicely. The only slight difficulty arises when you use the function players.get(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:
Player plr = (Player)players.get(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 all the players move is
for (int i = 0; i < players.size(); i++) {
Player plr = (Player)players.get(i);
plr.makeMove();
}
The two lines inside the for loop can be combined to a single line:
((Player)players.get(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)players.get(i)" are required because of Java's precedence rules. The parentheses force the type-cast to be performed before the makeMove() method is called.
In Section 5.4, I displayed an applet, ShapeDraw, that uses ArrayLists. Here is another version of the same idea, simplified to make it easier to see how ArrayLists are being used. Right-click the large white drawing area to add a colored rectangle. (On a Macintosh, Command-click the drawing area.) The color of the rectangle is given by the "rainbow palette" along the bottom of the applet. Click the palette to select a new color. Click and drag rectangles with the left mouse button. Hold down the Alt or Option key and click on a rectangle to delete it. Shift-click a rectangle to move it out in front of all the other rectangles.
The source code for this applet is in the file SimpleDrawRects.java. You should be able to follow it in its entirety. (If you've read Chapter 7, you can also take a look at the file RainbowPalette.java, which defines a custom component that is used for the colored palette in this applet.) 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 class, ColoredRect, that is defined as
class ColoredRect {
// Holds data for one colored rectangle.
int x,y; // Upper left corner of the rectangle.
int width,height; // size of the rectangle.
Color color; // Color of the rectangle.
}
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, as shown in the applet):
for (int i = 0; i < rects.size(); i++) {
ColoredRect rect = (ColoredRect)rects.get(i);
g.setColor( rect.color );
g.fillRect( rect.x, rect.y, rect.width, rect.height);
g.setColor( Color.black );
g.drawRect( rect.x, rect.y, rect.width - 1, rect.height - 1);
}
To implement all the mouse operations in the applet, it must be possible to find the rectangle, if any, that contains the point where the user clicked the mouse. To do this, I wrote the function
ColoredRect findRect(int x, int y) {
// 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 the one that is returned.
for (int i = rects.size() - 1; i >= 0; i--) {
ColoredRect rect = (ColoredRect)rects.get(i);
if ( x >= rect.x && x < rect.x + rect.width
&& y >= rect.y && y < rect.y + rect.height )
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 rects.remove(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 rectangle to the last position in the list. This is done by removing the rectangle from its current position in the list and then adding it back at the end:
void bringToFront(ColoredRect rect) {
// If rect != null, move it out in front of the other
// rects by moving it to the last position in the ArrayList.
if (rect != null) {
rects.remove(rect);
rects.add(rect);
repaint();
}
}
This should be enough to give you the basic idea. You can look in the source code for more details.
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 12. Earlier versions of Java did not include ArrayList, but they did have a very similar class named java.util.Vector. 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 different 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:- vec.size() is a function that returns the number of elements currently in the vector.
- vec.addElement(obj) will add the Object, obj to the end of the vector. This is the same as the add() method of an ArrayList.
- vec.removeElement(obj) removes obj from the vector, if it occurs. Only the first occurrence is removed. This is the same as remove(obj) for an ArrayList.
- vec.removeElementAt(N) removes the N-th element, for an integer N. N must be in the range 0 to vec.size()-1. This is the same as remove(N) for an ArrayList.
- vec.setSize(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 filled with null. The ArrayList class does not have a setSize() method.
The Vector class includes many more methods, but these are probably the most commonly used.