Chapter 8

Arrays and Array Lists


Chapter Goals


Arrays

Arrays

Arrays

Arrays

Syntax 8.1: Array Construction

 
new typeName[length]

Example:

 
new double[10]

Purpose:

To construct an array with a given number of elements

Syntax 8.2: Array Element Access

 
arrayReference[index]

Example:

  data[2]

Purpose:

To access an element in an array

Self Check

  1. What elements does the data array contain after the following statements?
    double[] data = new double[10];
    for (int i = 0; i < data.length; i++) data[i] = i * i;
  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.
    1. double[] a = new double[10];
      System.out.println(a[0]);
    2. double[] b = new double[10];
      System.out.println(b[10]);
    3. double[] c;
      System.out.println(c[0]);

Answers

  1. 0, 1, 4, 9, 16, 25, 36, 49, 64, 81, but not 100
    1. 0
    2. a run-time error: array index out of bounds
    3. a compile-time error: c is not initialized

Array Lists

Retrieving Array List Elements

Adding Elements

Removing Elements

File ArrayListTester.java

File BankAccount.java


Output

   size=3
first account number=1008
last account number=1729

Self Check

  1. How do you construct an array of 10 strings? An array list of strings?
  2. 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);

Answers

  1. new String[10];
    new ArrayList<String>();
  2. names contains the strings "B" and "C" at positions 0 and 1

Wrappers

Wrappers

Auto-boxing


Self Check

  1. What is the difference between the types double and Double?
  2. Suppose data is an ArrayList<Double> of size > 0. How do you increment the element with index 0?

Answers

  1. double is one of the eight primitive types. Double is a class type.
  2. data.set(0, data.get(0) + 1);

The Generalized for Loop

The Generalized for Loop

Syntax 8.3: The "for each" Loop

 
for (Type variable : collection)
statement

Example:

 
for (double e : data)
sum = sum + e;

Purpose:

To execute a loop for each element in the collection. In each iteration, the variable is assigned the next element of the collection. Then the statement is executed.

Self Check

  1. Write a "for each" loop that prints all elements in the array data
  2. Why is the "for each" loop not an appropriate shortcut for the following ordinary for loop?
    for (int i = 0; i < data.length; i++) data[i] = i * i;

Answers

  1. for (double x : data) System.out.println(x);
  2. The loop writes a value into data[i]. The "for each" loop does not have the index variable i.

Simple Array Algorithms: Counting Matches

Check all elements and count the matches until you reach the end of the array list.

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

Simple Array Algorithms: Finding a Value

Check all elements until you have found a match.

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

Simple Array Algorithms: Finding the Maximum or Minimum


File Bank.java

File BankTester.java


Output

   2 accounts with balance >= 15000.0
Account with number 1015 has balance 10000.0
Account with number 1001 has the largest balance.

Self Check

  1. What does the find method do if there are two bank accounts with a matching account number?
  2. Would it be possible to use a "for each" loop in the getMaximum method?

Answers

  1. It returns the first match that it finds
  2. Yes, but the first comparison would always fail

Two-Dimensional Arrays

A Tic-Tac-Toe Board

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] = " ";

File TicTacToe.java

File TicTacToeTester.java

Output

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

  1. How do you declare and initialize a 4-by-4 array of integers?
  2. How do you count the number of spaces in the tic-tac-toe board?

Answers

  1. int[][] array = new int[4][4];
  2. int count = 0;
    for (int i = 0; i < ROWS; i++)
    for (int j = 0; j < COLUMNS; j++)
    if (board[i][j] == ' ') count++;

Copying Arrays: Copying Array References

Copying Arrays: Cloning Arrays

Copying Arrays: Copying Array Elements

System.arraycopy(from, fromStart, to, toStart, count);
 

Adding an Element to an Array

System.arraycopy(data, i, data, i + 1, data.length - i - 1);
data[i] = x;

 

Removing an Element from an Array

System.arraycopy(data, i + 1, data, i, data.length - i - 1);
 

Growing an Array

Growing an Array


Self Check

  1. How do you add or remove elements in the middle of an array list?
  2. Why do we double the length of the array when it has run out of space rather than increasing it by one element?

Answers

  1. Use the insert and remove methods.
  2. Allocating a new array and copying the elements is time-consuming. You wouldn't want to go through the process every time you add an element.

Make Parallel Arrays into Arrays of Objects

Make Parallel Arrays into Arrays of Objects

Partially Filled Arrays

Partially Filled Arrays


An Early Internet Worm