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

> (Applet "ReverseIntsConsole" would be displayed here
> if Java were available.)

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

> (Applet "SimpleDrawRects" would be displayed here
> if Java were available.)

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

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