Chapter 7 – Arrays and Array Lists

Chapter Goals

To become familiar with using arrays and array lists
To learn about wrapper classes, auto-boxing and the generalized for loop
To study common array algorithms
To learn how to use two-dimensional arrays
To understand when to choose array lists and arrays in your programs
To implement partially filled arrays
To understand the concept of regression testing

Arrays

Array: Sequence of values of the same type
Construct array:
```
new double[10]
```
Store in variable of type double[]:
```
double[] values = new double[10];
```
When array is created, all values are initialized depending on array type:
- Numbers: 0
- boolean: false
- Object References: null

Arrays

Use [] to access an element:

values[2] = 29.95;

Arrays

Using the value stored:

System.out.println("The value of at index is " + values[2]);

Get array length as values.length (Not a method!)
Index values range from 0 to length - 1

Accessing a nonexistent element results in a bounds error:

double[] values = new double[10];
values[10] = 29.95; // ERROR

Limitation: Arrays have fixed length

Declaring Arrays

Syntax 7.1 Arrays

Self Check 7.1

What elements does the values array contain after the following statements?

double[] values = new double[10];
for (int i = 0; i < values.length; i++) values[i] = i * i;

Answer: 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, but not 100

Self Check 7.2

What do the following program segments print? Or, if there is an error, describe the error and specify whether it is detected at compile-time or at run-time.

double[] a = new double[10];
System.out.println(a[0]);

double[] b = new double[10];
System.out.println(b[10]);

```
double[] c;
System.out.println(c[0]);
```

Answer:
1. 0
2. a run-time error: array index out of bounds
3. a compile-time error: c is not initialized

Make Parallel Arrays into Arrays of Objects

// Don't do this
int[] accountNumbers;
double[] balances;

Make Parallel Arrays into Arrays of Objects

Avoid parallel arrays by changing them into arrays of objects:

BankAccount[] accounts;

Array Lists

ArrayList class manages a sequence of objects
Can grow and shrink as needed
ArrayList class supplies methods for many common tasks, such as inserting and removing elements

ArrayList is a generic class:

ArrayList<T>

collects objects of type parameter T:

ArrayList<String> names = new ArrayList<String>();
names.add("Emily");
names.add("Bob");
names.add("Cindy");

size method yields number of elements

Adding Elements

To add an object to the end of the array list, use the add method:

names.add("Emily"); 
names.add("Bob"); 
names.add("Cindy");

Retrieving Array List Elements

To obtain the value an element at an index, use the get method
Index starts at 0
String name = names.get(2); // gets the third element of the array list
Bounds error if index is out of range

Most common bounds error:

int i = names.size();
name = names.get(i); // Error
//legal index values are 0. . .i-1

Setting Elements

To set an element to a new value, use the set method:
```
names.set(2, “Carolyn”);
```

Removing Elements

To remove an element at an index, use the remove method:

names.remove(1);

Adding and Removing Elements

names.add("Emily"); 
names.add("Bob");
names.add("Cindy");
names.set(2, "Carolyn"); 
names.add(1, "Ann"); 
names.remove(1);

Working with Array Lists

ArrayList<String> names = new ArrayList<String>();	Constructs an empty array list that can hold strings.
names.add("Ann"); names.add("Cindy");	Adds elements to the end.
System.out.println(names);	Prints `[Ann, Cindy]`.
names.add(1, "Bob");	Inserts an element at index 1. `names` is now `[Ann, Bob, Cindy]`.
names.remove(0);	Removes the element at index 0. `names` is now `[Bob, Cindy]`.
names.set(0, "Bill");	Replaces an element with a different value. `names` is now `[Bill, Cindy]`.
String name = names.get(i);	Gets an element.
String last = names.get(names.size() - 1);	Gets the last element.
ArrayList<Integer> squares = new ArrayList<Integer>(); for (int i = 0; i < 10; i++) { squares.add(i * i); }	Constructs an array list holding the first ten squares.

Syntax 7.2 Array Lists

ch07/arraylist/ArrayListTester.java

ch07/arraylist/BankAccount.java

Program Run:

Size: 3
Expected: 3
First account number: 1008
Expected: 1008
Last account number: 1729
Expected: 1729

Self Check 7.3

How do you construct an array of 10 strings? An array list of strings?

Answer:

new String[10];
new ArrayList<String>();

Self Check 7.4

What is the content of names after the following statements?

ArrayList<String> names = new ArrayList<String>();
names.add("A");
names.add(0, "B");
names.add("C");
names.remove(1);

Answer: names contains the strings "B" and "C" at positions 0 and 1

Wrapper Classes

For each primitive type there is a wrapper class for storing values of that type:
```
Double d = new Double(29.95);
```
Wrapper objects can be used anywhere that objects are required instead of primitive type values:
```
ArrayList<Double> values = new ArrayList<Double>();
```

Wrapper Classes

There are wrapper classes for all eight primitive types:

Auto-boxing

Auto-boxing: Automatic conversion between primitive types and the corresponding wrapper classes:

Double d = 29.95; // auto-boxing; same as Double d = new Double(29.95);
double x = d; // auto-unboxing; same as double x = d.doubleValue();

Auto-boxing even works inside arithmetic expressions:
```
d = d + 1;
```
Means:
- auto-unbox d into a double
- add 1
- auto-box the result into a new Double
- store a reference to the newly created wrapper object in d

Auto-boxing and Array Lists

To collect numbers in an array list, use the wrapper type as the type parameter, and then rely on auto-boxing:
```
ArrayList<Double> values = new ArrayList<Double>(); 
values.add(29.95); 
double x = values.get(0);
```
Storing wrapped numbers is quite inefficient
- Acceptable if you only collect a few numbers
- Use arrays for long sequences of numbers or characters

Self Check 7.5

What is the difference between the types double and Double?

Answer: double is one of the eight primitive types. Double is a class type.

Self Check 7.6

Suppose values is an ArrayList<Double> of size > 0. How do you increment the element with index 0?

Answer: values.set(0, values.get(0) + 1);

The Enhanced `for` Loop

Traverses all elements of a collection:

double[] values = . . .;
double sum = 0;
for (double element : values)
{
   sum = sum + element;
}

Read the loop as for each element in values

Traditional alternative:

double[] values = . . .;
double sum = 0;
for (int i = 0; i < values.length; i++)
{
   double element = values[i];
   sum = sum + element;
}

The Enhanced `for` Loop

Works for ArrayLists too:

ArrayList<BankAccount> accounts = . . . ;
double sum = 0;
for (BankAccount account : accounts)
{
   sum = sum + account.getBalance();
}

Equivalent to the following ordinary for loop:

double sum = 0;
for (int i = 0; i < accounts.size(); i++)
{
   BankAccount account = accounts.get(i);
   sum = sum + account.getBalance();
}

The Enhanced `for` Loop

The for each loop does not allow you to modify the contents of an array:

for (double element : values) 
{ 
   element = 0; // ERROR—this assignment does not modify array elements 
}

Must use an ordinary for loop:

for (int i = 0; i < values.length; i++) 
{ 
   values[i] = 0; // OK 
}

Syntax 7.3 The for each Loop

Self Check 7.7

Write a for each loop that prints all elements in the array values.

Answer:

for (double element : values) System.out.println(element);

Self Check 7.8

What does this for each loop do?

int counter = 0; 
for (BankAccount a : accounts) 
{ 
   if (a.getBalance() == 0) { counter++; } 
}

Answer: It counts how many accounts have a zero balance.

Partially Filled Arrays

Array length = maximum number of elements in array
Usually, array is partially filled
Need companion variable to keep track of current size

Uniform naming convention:

final int VALUES_LENGTH = 100;
double[] values = new double[VALUES_LENGTH];
int valuesSize = 0;

Update valuesSize as array is filled:
```
values[valuesSize] = x;
valuesSize++;
```

Partially Filled Arrays

Example: Read numbers into a partially filled array:

int valuesSize = 0; 
Scanner in = new Scanner(System.in); 
while (in.hasNextDouble()) 
{ 
   if (valuesSize < values.length) 
   { 
      values[valuesSize] = in.nextDouble(); 
      valuesSize++; 
   } 
}

To process the gathered array elements, use the companion variable, not the array length:
```
for (int i = 0; i < valuesSize; i++) 
{ 
   System.out.println(values[i]); 
}
```

Self Check 7.9

Write a loop to print the elements of the partially filled array values in reverse order, starting with the last element.

Answer:

for (int i = valuesSize - 1; i >= 0; i--)
   System.out.println(values[i]);

Self Check 7.10

How do you remove the last element of the partially filled array values?

Answer:
```
valuesSize--;
```

Self Check 7.11

Why would a programmer use a partially filled array of numbers instead of an array list?

Answer: You need to use wrapper objects in an ArrayList<Double>, which is less efficient.

Common Array Algorithm: Filling

Fill an array with zeroes:

for (int i = 0; i < values.length; i++) 
{ 
   values[i] = 0; 
}

Fill an array list with squares (0, 1, 4, 9, 16, ...):

for (int i = 0; i < values.size(); i++) 
{ 
   values.set(i, i * i); 
}

Common Array Algorithm: Computing Sum and Average

To compute the sum of all elements, keep a running total:

double total = 0; 
for (double element : values) 
{ 
   total = total + element; 
}

To obtain the average, divide by the number of elements:

double average = total / values.size(); // For an array list

Be sure to check that the size is not zero

Common Array Algorithm: Counting Matches

Check all elements and count the matches until you reach the end

Example: Count the number of accounts whose balance is at least as much as a given threshold:

public class Bank
{
   private ArrayList<BankAccount> accounts;
   
   public int count(double atLeast)
   {
      int matches = 0;
      for (BankAccount account : accounts)
      {
         if (account.getBalance() >= atLeast) matches++; // Found a match
      }
      return matches;
   }
   . . .
}

Common Array Algorithm: Finding the Maximum or Minimum

Initialize a candidate with the starting element
Compare candidate with remaining elements
Update it if you find a larger or smaller value

Example: Find the account with the largest balance in the bank:

BankAccount largestYet = accounts.get(0); 
for (int i = 1; i < accounts.size(); i++) 
{ 
   BankAccount a = accounts.get(i); 
   if (a.getBalance() > largestYet.getBalance()) 
      largestYet = a; 
} 
return largestYet;

Works only if there is at least one element in the array list — if list is empty, return null:
```
if (accounts.size() == 0) return null; 
BankAccount largestYet = accounts.get(0); 
. . . 
```

Common Array Algorithm: Searching for a Value

Check all elements until you have found a match

Example: Determine whether there is a bank account with a particular account number in the bank:

public class Bank
{
   public BankAccount find(int accountNumber)
   {
      for (BankAccount account : accounts)
      {
         if (account.getAccountNumber() == accountNumber) // Found a match
            return account;
      }
      return null; // No match in the entire array list
   }
   . . .
}

This search process is called a linear search

Common Array Algorithm: Locating the Position of an Element

Problem: Locate the position of an element so that you can replace or remove it
Use a variation of the linear search algorithm, but remember the position instead of the matching element

Example: Locate the position of the first element that is larger than 100:

int pos = 0; 
boolean found = false; 
while (pos < values.size() && !found) 
{ 
   if (values.get(pos) > 100) { found = true; } 
   else { pos++; } 
} 
if (found) { System.out.println("Position: " + pos); } 
else { System.out.println("Not found"); }

Common Array Algorithm: Removing an Element

Array list ⇒ use method remove
Unordered array ⇒
1. Overwrite the element to be removed with the last element of the array
2. Decrement the variable tracking the size of the array
```
values[pos] = values[valuesSize - 1]; 
valuesSize--;
```
Ordered array ⇒
1. Move all elements following the element to be removed to a lower index
2. Decrement the variable tracking the size of the array
```
for (int i = pos; i < valuesSize - 1; i++) 
{ 
   values[i] = values[i + 1]; 
} 
valuesSize--;
```

Common Array Algorithm: Removing an Element

Animation 7.1: Removing from an Array

Link to Flash animation

Common Array Algorithm: Inserting an Element

Array list ⇒ use method add
Unordered array ⇒
1. Insert the element as the last element of the array
2. Increment the variable tracking the size of the array
```
if (valuesSize < values.length) 
{ 
   values[valuesSize] = newElement; 
   valuesSize++; 
}
```
Ordered array ⇒
1. Start at the end of the array, move that element to a higher index, then move the one before that, and so on until you finally get to the insertion location
2. Insert the element
3. Increment the variable tracking the size of the array
```
if (valuesSize < values.length) 
{ 
   for (int i = valuesSize; i > pos; i--) 
   { 
      values[i] = values[i - 1]; 
   } 
   values[pos] = newElement; 
   valuesSize++; 
}
```

Common Array Algorithm: Inserting an Element

Animation 7.2: Inserting into an Array

Link to Flash animation

Common Array Algorithm: Copying an Array

Copying an array variable yields a second reference to the same array:

double[] values = new double[6]; 
. . .  // Fill array 
double[] prices = values;

To make a true copy of an array, call the Arrays.copyOf method:
```
double[] prices = Arrays.copyOf(values, values.length);  
```

Common Array Algorithm: Growing an Array

To grow an array that has run out of space, use the Arrays.copyOf method:
```
values = Arrays.copyOf(values, 2 * values.length);
```

Common Array Algorithm: Growing an Array

Example: Read an arbitrarily long sequence numbers into an array, without running out of space:

int valuesSize = 0; 
while (in.hasNextDouble()) 
{ 
   if (valuesSize == values.length) 
      values = Arrays.copyOf(values, 2 * values.length); 
   values[valuesSize] = in.nextDouble(); 
   valuesSize++;   
}

Common Array Algorithm: Printing Element Separators

When you display the elements of an array or array list, you usually want to separate them:
```
Ann | Bob | Cindy
```
Note that there is one fewer separator than there are elements

Print the separator before each element except the initial one (with index 0):

for (int i = 0; i < names.size(); i++) 
{ 
   if (i > 0) 
   { 
      System.out.print(" | "); 
   } 
   System.out.print(names.get(i)); 
}

ch07/bank/Bank.java

Bank class stores an array list of bank accounts
Methods of the Bank class use some of the previous algorithms

ch07/bank/BankTester.java

Program Run:

Count: 2
Expected: 2
Balance of matching account: 10000.0
Expected: 10000
Account with largest balance: 1001
Expected: 1001

Self Check 7.12

What does the find method do if there are two bank accounts with a matching account number?

Answer: It returns the first match that it finds.

Self Check 7.13

Would it be possible to use a for each loop in the getMaximum method?

Answer: Yes, but the first comparison would always fail.

Self Check 7.14

When printing separators, we skipped the separator before the initial element. Rewrite the loop so that the separator is printed after each element, except for the last element.

Answer:

for (int i = 0; i < values.size(); i++) 
{ 
   System.out.print(values.get(i)); 
   if (i < values.size() - 1) 
   { 
      System.out.print(" | "); 
   } 
}

Now you know why we set up the loop the other way.

Self Check 7.15

The following replacement has been suggested for the algorithm that prints element separators:

System.out.print(names.get(0)); 
for (int i = 1; i < names.size(); i++)
   System.out.print(" | " + names.get(i));

What is problematic about this suggestion?

Answer: If names happens to be empty, the first line causes a bounds error.

Regression Testing

Test suite: a set of tests for repeated testing
Cycling: bug that is fixed but reappears in later versions
Regression testing: repeating previous tests to ensure that known failures of prior versions do not appear in new versions

ch07/regression/BankTester.java

Regression Testing: Input/Output Redirection

Store the inputs in a file
ch07/regression/input1.txt:
```
15000
2
1015
10000
```
Type the following command into a shell window:
```
java BankTester < input1.txt
```

Program Run:

Count: 2
Expected: 2
Balance of matching account: 10000
Expected: 10000

Output redirection:

java BankTester < input1.txt > output1.txt

Self Check 7.16

Suppose you modified the code for a method. Why do you want to repeat tests that already passed with the previous version of the code?

Answer: It is possible to introduce errors when modifying code.

Self Check 7.17

Suppose a customer of your program finds an error. What action should you take beyond fixing the error?

Answer: Add a test case to the test suite that verifies that the error is fixed.

Self Check 7.18

Why doesn't the BankTester program contain prompts for the inputs?

Answer: There is no human user who would see the prompts because input is provided from a file.

Therac-25 Facility

Two-Dimensional Arrays

When constructing a two-dimensional array, specify how many rows and columns are needed:

final int ROWS = 3;
final int COLUMNS = 3;
String[][] board = new String[ROWS][COLUMNS];

Access elements with an index pair:
```
board[1][1] = "x"; 
board[2][1] = "o";
```

Traversing Two-Dimensional Arrays

It is common to use two nested loops when filling or searching:

for (int i = 0; i < ROWS; i++)
   for (int j = 0; j < COLUMNS; j++)
      board[i][j] = " ";

You can also recover the array dimensions from the array variable:
- board.length is the number of rows
- board[0].length is the number of columns

Rewrite the loop for filling the tic-tac-toe board:

for (int i = 0; i < board.length; i++) 
   for (int j = 0; j < board[0].length; j++) 
      board[i][j] = " ";

ch07/twodim/TicTacToe.java

ch07/twodim/TicTacToeRunner.java

Program Run:

|   |
|   |
|   |
Row for x (-1 to exit): 1
Column for x: 2
|   |
|  x|
|   |
Row for o (-1 to exit): 0
Column for o: 0
|o  |
|  x|
|   |
Row for x (-1 to exit): -1

Self Check 7.19

How do you declare and initialize a 4-by-4 array of integers?

Answer:
```
int[][] array = new int[4][4];
```

Self Check 7.20

How do you count the number of spaces in the tic-tac-toe board?

Answer:

int count = 0;
for (int i = 0; i < ROWS; i++)
   for (int j = 0; j < COLUMNS; j++)
      if (board[i][j] == ' ') count++;

Chapter 7 – Arrays and Array Lists

Chapter Goals

Arrays

Arrays

Arrays

Arrays

Declaring Arrays

Syntax 7.1 Arrays

Self Check 7.1

Self Check 7.2

Make Parallel Arrays into Arrays of Objects

Make Parallel Arrays into Arrays of Objects

Array Lists

Adding Elements

Retrieving Array List Elements

Setting Elements

Removing Elements

Adding and Removing Elements

Working with Array Lists

Syntax 7.2 Array Lists

ch07/arraylist/ArrayListTester.java

ch07/arraylist/BankAccount.java

Self Check 7.3

Self Check 7.4

Wrapper Classes

Wrapper Classes

Auto-boxing

Auto-boxing and Array Lists

Self Check 7.5

Self Check 7.6

The Enhanced for Loop

The Enhanced for Loop

The Enhanced for Loop

Syntax 7.3 The for each Loop

Self Check 7.7

Self Check 7.8

Partially Filled Arrays

Partially Filled Arrays

Partially Filled Arrays

Self Check 7.9

Self Check 7.10

Self Check 7.11

Common Array Algorithm: Filling

Common Array Algorithm: Computing Sum and Average

Common Array Algorithm: Counting Matches

Common Array Algorithm: Finding the Maximum or Minimum

Common Array Algorithm: Searching for a Value

Common Array Algorithm: Locating the Position of an Element

Common Array Algorithm: Removing an Element

Common Array Algorithm: Removing an Element

Animation 7.1: Removing from an Array

Common Array Algorithm: Inserting an Element

Common Array Algorithm: Inserting an Element

Animation 7.2: Inserting into an Array

Common Array Algorithm: Copying an Array

Common Array Algorithm: Growing an Array

Common Array Algorithm: Growing an Array

Common Array Algorithm: Printing Element Separators

ch07/bank/Bank.java

ch07/bank/BankTester.java

Self Check 7.12

Self Check 7.13

Self Check 7.14

Self Check 7.15

Regression Testing

ch07/regression/BankTester.java

Regression Testing: Input/Output Redirection

Self Check 7.16

Self Check 7.17

Self Check 7.18

Therac-25 Facility

Two-Dimensional Arrays

Traversing Two-Dimensional Arrays

ch07/twodim/TicTacToe.java

ch07/twodim/TicTacToeRunner.java

Self Check 7.19

Self Check 7.20

The Enhanced `for` Loop

The Enhanced `for` Loop

The Enhanced `for` Loop