Big Java 4

Chapter 7 – Arrays and Array Lists

Chapter Goals

identical train cars

Arrays

Arrays

Arrays

declare, initialize, modify an array

Figure 1 An Array of Size 10

Syntax 7.1 Arrays

Array syntax

Arrays

Arrays - Bounds Error

Declaring Arrays

array delarations

Array References

Using Arrays with Methods

Partially Filled Arrays

Partially Filled Arrays

Partially Filled Arrays

partially-filled array

Partially Filled Arrays

Self Check 7.1

Declare an array of integers containing the first five prime numbers

Self Check 7.2

Assume the array primes has been initialized as described in Self Check 1. What does it contain after executing the following loop?
for (int i = 0; i < 2; i++)
{
    primes[4 - i] = primes[i];
}

Self Check 7.3

Assume the array primes has been initialized as described in Self Check 1. What does it contain after executing the following loop?
for (int i = 0; i < 5; i++)
{
   primes[i]++;
}

Self Check 7.4

Given the declaration
int[] values = new int[10];
write statements to put the integer 10 into the elements of the array values with the lowest and the highest valid index.

Self Check 7.5

Declare an array called words that can hold ten elements of type String.

Self Check 7.6

Declare an array containing two strings, "Yes", and "No".

Self Check 7.7

Can you produce the output on page 312 without storing the inputs in an array, by using an algorithm similar to the algorithm for finding the maximum in Section 6.7.5?

Self Check 7.8

Declare a method of a class Lottery that returns a combination of n numbers. You don’t need to implement the method.

Make Parallel Arrays into Arrays of Objects

Make Parallel Arrays into Arrays of Objects

Avoid parallel arrays by changing them into arrays of objects:
BankAccount[] accounts;

turn parallel arrays into objects

Figure 5

The Enhanced for Loop

The Enhanced for Loop

Syntax 7.2 The Enhanced for Loop

Syntax of enhanced for loop

Self Check 7.9

What does this enhanced for loop do?
int counter = 0;
for (double element : values)
{
   if (element == 0) { counter++; }
}

Self Check 7.10

Write an enhanced for loop that prints all elements in the array values.

Self Check 7.11

Write an enhanced for loop that multiplies all elements in a double[] array named factors, accumulating the result in a variable named product.

Self Check 7.12

Why is the enhanced for loop not an appropriate shortcut for the following basic for loop?
for (int i = 0; i < values.length; i++) { values[i] = i * i; }

Common Array Algorithm: Filling

Common Array Algorithm: Sum and Average

Common Array Algorithm: Maximum or Minimum

Common Array Algorithm: Element Separators

Common Array Algorithm: Linear Search

Common Array Algorithm: Linear Search

Common Array Algorithm: Removing an Element

Problem: To remove the element with index pos from the array values with number of elements currentSize.

Common Array Algorithm: Removing an Element

Common Array Algorithm: Inserting an Element

Common Array Algorithm: Inserting an Element

Common Array Algorithm: Swapping Elements

Common Array Algorithm: Swapping Elements

swapping

Figure 10 Swapping Array Elements

Common Array Algorithm: Copying an Array

Common Array Algorithm: Growing an Array

Reading Input

section_3/LargestInArray.java

Your browser does not support this feature Program Run:

Self Check 7.13

Given these inputs, what is the output of the LargestInArray program?
20 10 20 Q

Self Check 7.14

Write a loop that counts how many elements in an array are equal to zero.

Self Check 7.15

Consider the algorithm to find the largest element in an array. Why don’t we initialize largest and i with zero, like this?
double largest = 0;
for (int i = 0; i < values.length; i++)
{
   if (values[i] > largest)
   {
      largest = values[i];
   }
}

Self Check 7.16

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.

Self Check 7.17

What is wrong with these statements for printing an array with separators?
System.out.print(values[0]);
for (int i = 1; i < values.length; i++)
{
   System.out.print(", " + values[i]);
}

Self Check 7.18

When finding the position of a match, we used a while loop, not a for loop. What is wrong with using this loop instead?
for (pos = 0; pos < values.length && !found; pos++)
{
   if (values[pos] > 100)
   {
      found = true;
   }
}

Self Check 7.19

When inserting an element into an array, we moved the elements with larger index values, starting at the end of the array. Why is it wrong to start at the insertion location, like this?
for (int i = pos; i < currentSize - 1; i++)
{
   values[i + 1] = values[i];
}

Problem Solving: Adapting Algorithms

Problem Solving: Adapting Algorithms - continued

Problem Solving: Adapting Algorithms - continued

Self Check 7.20

Section 7.3.6 has two algorithms for removing an element. Which of the two should be used to solve the task described in this section?

Self Check 7.21

It isn’t actually necessary to remove the minimum in order to compute the total score. Describe an alternative.

Self Check 7.22

How can you print the number of positive and negative values in a given array, using one or more of the algorithms in Section 6.7?

Self Check 7.23

How can you print all positive values in an array, separated by commas?

Self Check 7.24

Consider the following algorithm for collecting all matches in an array: int matchesSize = 0;
for (int i = 0; i < values.length; i++)
{
   if (values[i] fulfills the condition)
   {
      matches[matchesSize] = values[i];
      matchesSize++;
   }
}
How can this algorithm help you with Self Check 23?

Problem Solving: Discovering Algorithms by Manipulating Physical Objects

Problem Solving: Discovering Algorithms by Manipulating Physical Objects

Problem Solving: Discovering Algorithms by Manipulating Physical Objects

Problem Solving: Discovering Algorithms by Manipulating Physical Objects

Self Check 7.25

Walk through the algorithm that we developed in this section, using two paper clips to indicate the positions for i and j. Explain why there are no bounds errors in the pseudocode.

Self Check 7.26

Take out some coins and simulate the following pseudocode, using two paper clips to indicate the positions for i and j.
i = 0
j = size - 1
While (i < j)
   Swap elements at positions i and j
   i++
   j--
What does the algorithm do?

Self Check 7.27

Consider the task of rearranging all elements in an array so that the even numbers come first. Otherwise, the order doesn’t matter. For example, the array

1 4 14 2 1 3 5 6 23

could be rearranged to

4 2 14 6 1 5 3 23 1

Using coins and paperclips, discover an algorithm that solves this task by swapping elements, then describe it in pseudocode.

Self Check 7.28

Discover an algorithm for the task of Self Check 27 that uses removal and insertion of elements instead of swapping.

Self Check 7.29

deck of cards

Consider the algorithm in Section 6.7.5 that finds the largest element in a sequence of inputs—not the largest element in an array. Why is this algorithm better visualized by picking playing cards from a deck rather than arranging toy soldiers in a sequence?

 

Two-Dimensional Arrays

Two-Dimensional Arrays

Syntax 7.3 Two-Dimensional Array Declaration

syntax of 2-d array

Accessing Elements

Accessing Elements

Locating Neighboring Elements

Accessing Rows and Columns

Accessing Rows and Columns

section_6/Medals.java

Your browser does not support this feature Program Run:

Self Check 7.30

What results do you get if you total the columns in our sample data?

Self Check 7.31

Consider an 8 × 8 array for a board game:

int[][] board = new int[8][8];

Using two nested loops, initialize the board so that zeros and ones alternate, as
on a checkerboard:

0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1
. . .
1 0 1 0 1 0 1 0

Hint: Check whether i + j is even.

Self Check 7.32

Declare a two-dimensional array for representing a tic-tac-toe board. The board has three rows and columns and contains strings "x", "o", and " ".

Self Check 7.33

Write an assignment statement to place an "x" in the upper-right corner of the tic-tac-toe board in Self Check 32.

Self Check 7.34

Which elements are on the diagonal joining the upper-left and the lower-right corners of the tic-tac-toe board in Self Check 32?

Array Lists

Syntax 7.4 Array Lists

syntax of array list

Declaring and Using Array Lists

Declaring and Using Array Lists

Declaring and Using Array Lists

Declaring and Using Array Lists

Declaring and Using Array Lists

inserting elements into an array list

Figure 18 Adding and Removing Elements in the Middle of an Array List

Using the Enhanced for Loop with Array Lists

Copying Array Lists

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.

Wrapper Classes

Wrapper Classes

Using Array Algorithms with Array Lists

Storing Input Values in an Array List

Removing Matches

Removing Matches

Choosing Between Array Lists and Arrays

Choosing Between Array Lists and Arrays

comparing arrays and arraylists

section_7/LargestInArrayList.java

Your browser does not support this feature Program Run:

Self Check 7.35

Declare an array list primes of integers that contains the first five prime numbers (2, 3, 5, 7, and 11).

Self Check 7.36

Given the array list primes declared in Self Check 35, write a loop to print its elements in reverse order, starting with the last element.

Self Check 7.37

What does the array list names contain after the following statements?
ArrayList<String> names = new ArrayList<String>;
names.add("Bob");
names.add(0, "Ann");
names.remove(1);
names.add("Cal");

Self Check 7.38

What is wrong with this code snippet?
ArrayList<String> names;
names.add(Bob);

Self Check 7.39

Consider this method that appends the elements of one array list to another:
public void append(ArrayList<String> target, ArrayList<String> source)
{
   for (int i = 0; i < source.size(); i++)
   {
      target.add(source.get(i));
   }
}
What are the contents of names1 and names2 after these statements?
ArrayList<String> names1 = new ArrayList<String>();
names1.add("Emily");
names1.add("Bob");
names1.add("Cindy");
ArrayList<String> names2 = new ArrayList<String>();
names2.add("Dave");
append(names1, names2);

Self Check 7.40

Suppose you want to store the names of the weekdays. Should you use an array list or an array of seven strings?

Self Check 7.41

The ch07/section_7 directory of your source code contains an alternate implementation of the problem solution in How To 7.1 on page 334. Compare the array and array list implementations. What is the primary advantage of the latter?

Regression Testing

Regression Testing - Two Approaches

section_8/ScoreTester.java

Generic tester:

Your browser does not support this feature

Input and Output Redirection

Self Check 7.42

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

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

Why doesn't the ScoreTester program contain prompts for the inputs?
  • Answer: There is no human user who would see the prompts because input is provided from a file.