UNIT 6
Array
IN THIS UNIT
Summary: Sometimes a simple variable is not enough. To solve certain problems, you need a list of variables or objects. The array, the two-dimensional array, and the ArrayList are three complex data structures that are tested on the AP Computer Science A Exam. You must learn the advantages and disadvantages of each of these data structures, know how to work with them, and be able to choose the best one for the job at hand. Programmers use algorithms extensively to write the code that will automate a process in a computer program. The algorithms described in this unit are some of the fundamental algorithms that you should know for the AP Computer Science A Exam. ArrayList and 2D array will be discussed in Units 7 and 8.
Key Ideas
An array is a data structure that can store a list of variables of the same data type.
An array is not resizable once it is created.
To traverse a data structure means to visit each element in the structure.
The enhanced for loop (for-each loop) is a special looping structure that can be used by either arrays or ArrayLists.
An algorithm is a set of steps that when followed complete a task.
Pseudocode is a hybrid between an algorithm and actual Java code.
Efficient code performs a task in the fastest way.
The accumulate algorithm traverses a list, adding each value to a total.
The find-highest algorithm traverses and compares each value in the list to determine which one is the largest.
What Is a Data Structure?
Have you ever dreamed about having the high score in the “Top Scores” of a game? How does Facebook keep track of your friends? How does Vine know what video to loop next? All of these require the use of a complex data structure.
Simple Data Structure Versus Complex Data Structure
As programmers, we use data structures to store information. A primitive variable is an example of a simple data structure as it can store a single value to be retrieved later. A variable that can store a list of other variables is called a complex data structure.
Thinking of ways to represent physical objects by using virtual objects can be challenging. Really awesome programmers have the ability to visualize complex real-world situations and design data structures to represent these physical objects in a virtual way. In the drawing below, the programmer is trying to figure out a way to represent the choices from the lunch menu in a program by creating a complex data structure.
Three Important Complex Data Structures
There are three complex data structures that are tested on the AP Computer Science A Exam:
• The array (or one-dimensional array)
• The 2D array
• The ArrayList
The array will be explained in detail later in this unit, ArrayList will be explained in Unit 7, and 2D array will be explained in Unit 8, but for now, I want to give you an overview of which data structure would be the best choice for a given situation. You will want to become a master at deciding the best data structure for a particular situation. This normally comes with experience, but here are a few examples as to which one is the best under what circumstances.
The Array
Definition of an Array
The non-programming definition of an array is “an impressive display of a particular thing.” We use the word in common language when we say things like, “Wow, look at the wide array of phone cases at the mall!” It means that there is a group or list of things that are of the same kind.
An array (one-dimensional array) in Java is a complex data structure because it can store a list of primitives or objects. It also stores them in such a way that each of the items in the list can be referenced by an index. This means that the array assigns a number to each of the slots that holds each of the values. By doing this, the programmer can easily find the value that is stored in a slot, change it, print it, and so on. The values in the array are called the elements of the array. An array can hold any data type, primitive or object.
Declaring an Array and Initializing It Using a Predefined List of Data
There are two ways to create an array on the AP Computer Science A Exam. The first uses an initializer list. This technique is used when you already know the values that you are going to store in the list and you have no reason to add any more items. A pair of brackets, [ ], tells the compiler to create an array, not just a regular variable.
General Form for Creating an Array Using a Predefined List of Data
Notice the pair of brackets [ ] after dataType. The brackets signify this variable is a reference to an array object.
Example
Declare an array of String variables that represent food choices at a restaurant:
The graphic at the right is a visual representation of the foodChoices array. The strings representing the actual food choices are the elements in the array (Pizza, Cheeseburger, etc.) and each slot is assigned a number, called the index (0, 1, 2, etc.). The index is a number that makes it easy for the programmer to know what element is placed in what slot. The first index is always zero. The last index is always one less than the length of the array.
How to “Speak” Array
When talking about elements of an array, we say things like, “Pizza is the first element in the foodChoices array and its index is zero” or “The element at index 2 of the foodChoices array is Tacos.”
The length Field
After an array is created and initialized, you can ask it how many slots it has by using the length field. Think of the length as an instance variable for an array. Notice that the length does not have a pair of parentheses after it, because it is not a method.
Example
Find the length of the foodChoices array:
The length of an Array
The length field of an array returns the total number of slots that are set aside for that array. It does not return the total number of valid elements in the array. Also, since the first index of an array is always zero, the length of the array is always one more than the last index.
Declaring an Array Using the Keyword new
The second technique for creating an array is used when you know the length of the list, but you may not know all of the values that will go in the list. Again, a pair of brackets, [ ], is used to tell the compiler that you want to create an array, not just a regular variable.
General Form for Creating an Array Using the Keyword new
The number of slots is fixed and all of the elements in the array get the default value for the data type. You can also declare just an array reference variable and then use the keyword new to create the array later.
No Resizing an Array
An array cannot be resized after it is created.
Example
Create an array that will represent all of your semester grade point averages for all four years of high school. Let’s assume there are two semesters per year. This makes a total of eight semesters. So, let’s declare an array to hold eight double values and call the array myGPAs.
Ouch, all zeros. That hurts. No worries, we can change that. You see, when an array is created in this manner, all of the elements become whatever the default value is for that data type. The default value for a double is 0.0, the default value for an int is 0, for boolean it is false, and for a reference type it is null.
Now that the array is created, let’s put some valid numbers into it. In order to replace a value in an array, you need to know the correct index.
Let’s let index 0 represent the first semester of your freshman year and let’s suppose you earned a GPA of 3.62.
myGPAs[0] = 3.62; // puts 3.62 in slot 0
And, let’s suppose you earned a 3.75 for the second semester of your sophomore year.
myGPAs[3] = 3.75; // puts 3.75 in slot 3
Smart, but Not So Smart
The computer has no idea that these numbers represent the GPAs for a student in school. As far as it’s concerned, it is just storing a bunch of numbers in an array.
Example
Pick a random color from an array of color names:
The ArrayIndexOutOfBoundsException
The valid index values for an array are 0 through one less than the number of elements in the array, inclusive. If you ever accidently use an index that is too big (greater than or equal to the length of the array) or negative, you will get a run-time error called an ArrayIndexOutOfBoundsException.
Example
You declare an array of Circle objects and attempt to print the radius of the last circle. But you get an ArrayIndexOutOfBoundsException because your index is too large. Note: The length of the array is 6. The index of the last Circle object is 5. Then, write it the correct way:
Common Error
A common error is to accidentally set the index of an array to be the length of the array. The first index of the array is zero, so the last index of the array is length – 1.
Traversing an Array
To traverse an array means to move through each slot in the array, one at a time. The most common way to perform a traversal is to start with the first index and end with the last index. But that’s not the only way. You could start with the last index and move toward the first. You also could do all of the even indices first and then all of the odds. You get what I’m saying? Traversing an array just means that you visit every element at every index in an array.
Print the Contents of a One-Dimensional Array by Traversing It
Example
Print out the names of all your friends on Facebook using a for loop. By traversing the array from the first element to the last element, you can print each friend’s name.
Off-by-One Error
This is a logic error that every programmer has committed at some point. It means that in a loop of some kind, your index is off by one number. You either went one index too high or one index too low. This will result in an ArrayIndexOutOfBoundsException being thrown.
The Enhanced for Loop (the for-each Loop)
The enhanced for loop (aka the for-each loop) can also be used to traverse an array. It does not work the same way as the standard for loop. The for-each loop always starts at the beginning of the array and ends with the last element in the array. As the name indicates, the for-each loop iterates through each of the elements in the array, and for each element, the temporary variable “takes on” its value. The temporary variable is only a copy of the actual value and any changes to the temporary variable are not reflected in the actual value.
An enhanced for loop is simpler to write than a standard for loop since you don’t have to keep track of an index. The enhanced for loop is also less error-prone because Java automates the setup and processing of the loop control information. However, the enhanced for loop cannot be used to move through an array in reverse order, it cannot assign elements to an array, and since it does not have an index, it can’t track any position in the array.
General Form for the Enhanced for Loop (the for-each Loop)
There is no loop control variable for the enhanced for loop (it is a black box). You only have access to the elements in the array, not the index. Also, the data type of the temporary variable must be the same as the data type of the array.
Traversing a One-Dimensional Array Using the Enhanced for Loop
Example
Print out the names of all your friends on Facebook using a for-each loop. Note: friend is a temporary variable that is of the same data type as the data stored in the array.
OUTPUT
Mistake When Printing the Contents of an Array
Beginning programmers make the mistake of trying to print the contents of an array by printing the array reference variable. The result that is printed is garbage. This is because the reference variable only contains the address of where the array is; it does not store the elements of the array.
OUTPUT
Note: The best way to print the contents of an array is to traverse the array using either a for loop or a for-each loop.
How We Use Algorithms
In our daily lives, we develop and use algorithms all the time without realizing that we are doing it. For example, suppose your grandma calls you because she wants to watch Game of Thrones using the HBO GO app on her smart TV, but she can’t figure out how to do it. You would respond to her by saying, “Hi, Grandma, well, the first thing you have to do is turn your TV on,” then yada, yada, yada until finally you say, “Press play.”
What you have just done is developed a process for how to solve a problem. Now, if she insists that you write the steps down on a notecard so she can follow it anytime she wants to, then, you will be writing the algorithm for “How to watch Game of Thrones on grandma’s smart TV.”
Why Algorithms Are Important
The word algorithm can be simply defined as “a process to be followed to solve a problem.” Computer programmers use algorithms to teach the computer how to automate a process.
The number of algorithms to learn is infinite, so rather than attempting to learn all possible algorithms, my goal is to teach you how to write an algorithm. This will be handy on the AP Computer Science A Exam when you have to either analyze or generate code to accomplish something you’ve never done before. The two algorithm concepts in this book teach you how to think like a software developer.
Algorithm Versus Pseudocode Versus Real Java Code
Algorithms are great as directions for how to do something; however, they can’t be typed into a computer as a real Java program. The integrated development environment (IDE) needs to have the correct syntax so that the compiler can interpret your code properly. Can you imagine typing in the directions for Grandma as lines of code?
So, to solve this problem, programmers translate algorithms into pseudocode, which is a code-like language. This pseudocode is then translated into real code that the computer will understand.
This process is really powerful because as programming languages change, the algorithms can stay the same. In the examples that follow, I’ve written the code in Java, but it could’ve easily been written in C++, Python, etc.
Turning Your Ideas into Code
Pseudocode is an inner step when turning your ideas into code. It is code-like but does not use the syntax of any programming language.
The Swap Algorithm
Swapping is the concept of switching the values that are stored in two different variables. The ability to swap values is essential for sorting algorithms (explained in Unit 7). To complete a swap, you need to use a temporary variable to store one of the values.
Algorithm:
Step 1: Let a = 6 and b = 8
Step 2: Create a temporary variable called c
Step 3: Assign c the value of a
Step 4: Assign a the value of b
Step 5: Assign b the value of c
Step 6: Now, the value of a is 8 and b is now 6
Pseudocode:
set a = 6
set b = 8
c = a
a = b
b = c
Java Code:
The Copy Algorithm for the Array
Making a copy of an array means to create a brand-new object that is a duplicate of the original. This is different from creating a new array variable that references the original array. That was called making an alias. It is easy for new programmers to make the mistake of thinking that these two are the same.
Algorithm:
Step 1: Create an array that is the same length as the original
Step 2: Look at each of the values in the original array one at a time
Step 3: Assign the value in the copy to be the corresponding value in the original
Step 4: Continue until you reach the last index of the original array
Pseudocode:
Create an array called duplicate that has the same length as the original array for (iterate through each element in the original array)
Java Code 1: Java code using an array (for loop)
Java Code 2: Java code using an array (for-each loop)
Copying an Array Reference Versus Copying an Array
The following code demonstrates a common mistake when attempting to copy an array.
This code makes the reference variable copy refer to the same object that original refers to. This means that if you change a value in copy, it also changes the value in original. This code does not create a new object that is a duplicate of the original. This code makes both reference variables refer to the same object (the object that original refers to).
The Accumulate Algorithm
Suppose you have a list of all the baseball players on a team and you want to find the total number of hits that the team had. As humans, we can do this quite easily. Just add them up. But how do you teach a computer to add up all of the hits?
Algorithm:
Step 1: Create a variable called sum and set it equal to zero
Step 2: Look at each of the elements in the list
Step 3: Add the element to the sum
Step 4: Continue until you reach the end of the list
Step 5: Return the sum
Pseudocode:
Java Code 1: Using an array (for-each loop)
Java Code 2: Using an array (for loop)
The Find-Highest Algorithm
What is the highest score on your favorite video game? As more people play a game, how does the computer figure out what is the highest score in the list?
Solution 1: Let the highest be the first element in the list.
Algorithm:
Step 1: Create a variable called high and set it to the first element in the list
Step 2: Look at each of the scores in the list
Step 3: If the score is greater than the high score, then make it be the new high score
Step 4: Continue until you reach the end of the list
Step 5: Return the high score
Pseudocode:
Java Code 1: Using an array (for loop)
Java Code 2: Using an array (for-each loop)
Solution 2: Let the highest be an extremely low value.
There is an alternative solution to the high/low problem that you should know. To execute this alternative, we modify the first step in the previous algorithm.
Step 1: Create a variable called high and set it to a really, really small number.
This algorithm works as long as the really, really small number is guaranteed to be smaller than at least one of the numbers in the list. In Java, we can use the public fields from the Integer class to solve this problem.
Likewise, to solve the find-lowest problem, you could set the low to be a really, really big number.
Searching for the Smallest Item in a List
If we changed the previous example to find the lowest score in the list, then the comparator in the if statement would be changed to less than, <, instead of greater than, >.
〉 Rapid Review
The Array
• An array is a complex data structure that can store a list of data of the same data type.
• An array is also referred to as a one-dimensional (or 1D) array.
• An array can be created by assigning it a predetermined list.
• An array can be created by using the keyword new.
• An array can store either primitive data types or object reference types.
• Even though arrays are objects, they do not have methods.
• An array has one public field, called length.
• The length of the array refers to how many elements can be stored in the array and is decided when the array is created.
• The length of an array cannot be resized once it is declared. That is, an array cannot be made shorter or longer once it is created.
• The length field returns the total number of locations that exist in the array, and not the number of meaningful elements in the array.
• An element of an array refers to the item that is stored in the array.
• The index of an array refers to the position of an element in an array.
• The first index of an array is 0. The last index is its length - 1.
• Unused indices in an array automatically receive the default value for that data type.
• If an array contains objects, their default values are null. You need to instantiate an object for each element of the array before they can be used.
• Using an index that is not in the range of the array will throw an ArrayIndexOutOfBoundsException.
Traversing an Array
• Traversing an array refers to the process of visiting every element in the array.
• There are many options for traversing an array; however, the most common way is to start at the beginning and work toward the end.
• Based on the situation, there are times where you may want to traverse an array starting at the end and work toward the beginning.
• Sometimes you may want to traverse only a section of the array.
• When using a for loop to traverse an array, be sure to use length - 1 rather than length when accessing the last element in the array.
• The enhanced for loop iterates through each element in the array without using an index.
• The enhanced for loop is also known as the for-each loop.
• The enhanced for loop always starts with the first element and ends with the last.
• Use an enhanced for loop when you don’t need to know the index for each element and you don’t need to change the element in any way.
Algorithms and Pseudocode
• The purpose of this concept is to teach you how to translate an idea into code.
• An algorithm is a sequence of steps that, when followed, produces a specific result.
• Algorithms are an extremely important component of software development since you are teaching the computer how to do something all by itself.
• There are an infinite number of algorithms.
• Pseudocode is a hybrid between an algorithm and real code.
• Pseudocode does not use correct syntax and is not typed into an IDE.
• Pseudocode helps you translate an algorithm into real code since it is code-like and more refined than an algorithm.
• Programmers translate algorithms into pseudocode and then translate pseudocode into real code.
Swap Algorithm
• The swap algorithm allows you to switch the values in two different variables.
• To swap the values in two different variables, you must create a temporary variable to store one of the original variables.
• To swap num1 and num2, set temp = num1, let num1 = num2, and then let num2 = temp.
Copy Algorithm
• The copy algorithm is used to create a duplicate version of a data structure.
• It looks at each element in the original list and assigns it to the duplicate list.
• The duplicate is not an alias of the original; it is a new object that contains all of the same values as the original.
Accumulate Algorithm
• The accumulate algorithm finds the sum of all the items in a list.
• It looks at each element in the list one at a time, adding the value to a total.
Find-Highest Algorithm
• The find-highest algorithm finds the largest value in a list.
• It looks at each element in the list one at a time, comparing the value to the current high value.
• Common ways to implement this algorithm include initializing the highest value with the first value in the list or to an extremely small negative number.
• The find-highest algorithm can be modified to find the lowest item in a list.
〉 Review Questions
Basic Level
1. Consider the following code segment.
What is printed as a result of executing the code segment?
(A) 0
(B) 13
(C) 26
(D) 28
(E) 56
2. Consider the following code segment.
What is printed as a result of executing the code segment?
(A) 0
(B) 1
(C) 3
(D) 7
(E) 16
3. Consider the following code segment.
What is printed as a result of executing the code segment?
(A) 91
(B) 746
(C) 913
(D) 79416385
(E) 416385
4. Which segment of code will correctly count the number of even elements in an array arr?
I. 
II. 
III. 
(A) I only
(B) II only
(C) III only
(D) I and II only
(E) II and III only
5. Consider the following code segment.
What will be printed after the code segment is executed?
(A) 2 2 25 7 28
(B) 9 28 7 25 2
(C) 25 7 28 9 9
(D) 2 25 7 28 9
(E) Nothing will be printed. An ArrayIndexOutOfBoundsException will occur.
Advanced Level
6. Consider the following code segment.
What values are stored in array nums after executing the code segment?
(A) ArrayIndexOutOfBoundsException
(B) {2, 2, 3, 3, 4, 4, 5, 5}
(C) {0, 0, 1, 3, 5, 7, 9, 11}
(D) {0, 0, 1, 1, 3, 4, 5, 6}
(E) {0, 0, 1, 2, 2, 3, 4, 5}
7. During one iteration of the outer loop of the program segment below, how many times is the body of the inner loop executed?
(A) i + 1
(B) n – i
(C) n – i + 1
(D) i – n + 1
(E) n(i – 1)
8. A postcondition of a method is : arr[0] > arr[k] for all k such that 0 < k < arr.length. Which of the following is a correct conclusion?
(A) All values in the array are identical.
(B) The array is sorted in ascending order.
(C) The array is sorted in descending order.
(D) The smallest value in the array is arr[0].
(E) The largest value in the array is arr[0].
9. Consider the following code segment intended to count the number of elements in fruit that contain the letter “e”.
Which of the following substitutions for <statement> will cause the segment to work as intended?
(A) 
(B) 
(C) 
(D) 
(E) 
10. Consider two parallel arrays which contain the names and corresponding scores of players in a trivia game.
Which of the following code segments correctly prints the names and scores of all the players who scored above high?
11. Replace only highs and lows.
Write a method that replaces the highest values and the lowest values in a list. The method takes one parameter: an int array. The range of the numbers is 0–1000 (inclusive). If a value in the array is greater than 750, replace the value with 1000. If a value in the array is less than 250, replace it with 0. The method should return an int array of the same length as the parameter array and leave the original array untouched.
The array passed to the method:
The array returned by the method:
12. Determine the relative strength index of a stock.
The relative strength index (RSI) of a stock determines if the stock is overpriced or underpriced. The range of the RSI is from 0 to 100 (inclusive). If the value of the RSI is greater than or equal to 70, then the stock is determined to be overpriced and should be sold.
Write a method that takes an array of RSI values for a specific stock and determines when the stock is overpriced. The method has one parameter: a double array. The method should return a new array of the same length as the parameter array. If the value in the RSI array is greater than 70, set the value in the overpriced array to true. If the RSI value is less than or equal to 70, set the value in the overpriced array to false.
The RSI array that is sent to the method:
The overpriced array that is returned by the method:
13. Fill an array with even numbers.
Write a method that fills an array with random even numbers. The method takes two parameters: the number of elements in the array and the range of the random numbers (0–number inclusive).
result contains the following (results will change each time program is run):
〉 Answers and Explanations
Bullets mark each step in the process of arriving at the correct solution.
1. The answer is D.
• This is a for-each loop. Read it like this: “For each int (which I will call val) in values. . . .”
• The loop will go through each element of the array values and add it to number. Notice that number starts at 13.
2. The answer is D.
• values[total] = values[3] = -2. Remember to start counting at 0.
• 3 + -2 = 1, now total = 1.
• values [total] = values[1] = 6.
• 1 + 6 = 7 and that is what is printed.
3. The answer is C.
• Let’s lay out the array along with its indices.
• The first time through the loop, i = 3.
• values[3–2] = values [1] = 9 Print it.
• Next time through the loop, i = 5.
• values [5–2] = values [3] = 1 Print it.
• Next time through the loop, i = 7.
• Remember that even though the last index is 7, the length of the array is 8.
• values [7–2] = values[5] = 3 Print it.
• We exit the loop having printed "913".
4. The answer is B.
• Segment I checks if the index of the element is even, not the element itself.
• Segment II correctly checks if the element is even.
• Segment III correctly checks if the element is even, but because the increment is +2, it doesn’t check each element of the array.
5. The answer is A.
• The loop will shift each of the elements to the right starting at the second to last element.
6. The answer is D.
• On entering the loop, nums = {0, 0, 1, 1, 2, 2, 3, 3} and i = 3. Set nums[4] to 3.
• Now nums = {0, 0, 1, 1, 3, 2, 3, 3} and i = 4. Set nums[5] to 4.
• Now nums = {0, 0, 1, 1, 3, 4, 3, 3} and i = 5. Set nums[6] to 5.
• Now nums = {0, 0, 1, 1, 3, 4, 5, 3} and i = 6. Set nums[7] to 6.
• Now nums = {0, 0, 1, 1, 3, 4, 5, 6} and i = 7. nums.length - 1 = 7, so exit the loop.
7. The answer is B.
• The value can be found by using the starting and stopping values of the index.
• The inner loop begins at n, ends at i+1, and is incremented by 1.
• So, the number of times will be n – (i+1) – 1.
8. The answer is E.
• Since the condition arr[0] > arr[k] holds true for each element, element arr[0] must be the largest.
9. The answer is D.
• The indexOf method returns the index of the first occurrence of the string parameter.
• If the string parameter is not found the value –1 is returned.
10. The answer is C.
• Since we need to access the index of an element a standard for loop must be used, not a for-each loop.
• Only elements that are above high should be printed, so the inequality > must be used.
11. Replace only highs and lows.
Algorithm:
Step 1: Create a new array called temp that is the same length as the original
Step 2: Look at each of the scores in the list
Step 3: If the score is greater than 750, then store 1000 in the temp array
Step 4: If the score is less than 250, then store 0 in the temp array
Step 5: If the score is between 250 and 750, then store the score in the temp array
Step 6: Continue until you reach the end of the list
Step 7: Return the temp array
Pseudocode:
Java code:
12. Determine the relative strength index of a stock.
Algorithm:
Step 1: Create an array called temp that is the same length as the parameter array
Step 2: Look at each of the scores in the array
Step 3: If the score > 70, then set the corresponding element of the temp array to true; otherwise set it to false
Step 4: Continue until you reach the end of the list
Step 5: Return temp
Pseudocode:
create an integer array called temp that is the same length as the parameter array for (iterate through all the elements in the parameter array)
Java code:
13. Fill an array with randomly chosen even numbers. There are several ways to do this. Here is one.
Algorithm:
Step 1: Create an array called temp that is the same length as the parameter array
Step 2: Loop as many times as the length of the parameter array
Step 3: Generate a random number in the appropriate range
Step 4: While the random number is not even, generate a random number in the appropriate range
Step 5: Put the random number in the list
Step 6: Continue until you complete the correct number of iterations
Step 7: Return temp
Pseudocode:
create an integer array called temp that is the same length as the parameter array
Java code:
