AP Computer Science A -- Arrays

An array is a simple but powerful way to group and organize data. It can store a list of the same type of variables. When we have a large amount of information, such as list of 100 names, it is not practical to declare separate variables for each of data. Arrays solve this problem by letting us declare one variable that can hold many values. The array, two-dimensional array, and the ArrayList are three complex data structures that, along with their advantages, disadvantages and when to use each, are tested on the AP test.


Arrays | Arrays of Objects | Two-Dimensional Arrays | The ArrayList Class | Review


Arrays

an array example

An array in Java is a complex data structure because it can store a list of primitives or objects. The values in an array are called elements. It also stores them in such a way that each of item in the list can be referenced by an index.

In Java, an array is an object. The keyword new must be used in its creation. Array declarations look like this:

array example

type[] arrayName; //no array is created

This tells the compiler that arrayName contains a reference to an array containing type. However, the actual array object is not constructed by this declaration. The declaration merely declares a reference variable arrayName which, sometime in the future, is expected to refer to an array object. The [] is the array operator. The array operator (pair of brackets) tells the computer to create an array, not just a normal variable.

Often an array is declared and constructed in one statement, like this:

type[] arrayName = new type[ length ]; //array is created

This statement does two things:

  1. It tells the compiler that arrayName will refer to an array containing cells of type.
  2. It constructs an array object containing length number of cells.

For example, if I wanted to create an array of my friends, and I know that I have 4 friends, it would look like this:

String[] myFriends = new String[4];

I can then assign my each of my friends to an index position:

myFriends[0] = "Wanda";

myFriends[1] = "June";

You can also declare and initialize a small array with a list of objects when you already know what is going to populate the array. This the one case when the new operator is not required:

type[] arrayName = new type {value1, value2, value3, ....};

For example, if I wanted to create an array of friends, it might look at this:

String[] myFriends = {"Wanda", "June", "Eliza", "Terri"};

Referring to the array sample above, I would refer to "Wanda" as the first element in the myFriends array and its index is zero. The element at index 3 of the myFriends array is "Terri". Remember that the index position starts at zero.

Length Field

Once an array is created, it is not resizable. After an array is is 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. The length field is not a method and does not have a part of parenthesis at the end. 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 that array. Also, since the first index of any array is always zero, the length of the array is always one more the last index. Note that the length field is not a method so it does not contain the () at the end like a method does.

Example:

Find the length of the myFriends array:

int result = myFriends.length; //result is 4 (not 3)

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. The length of the array is always one more than the last index position because the index starts at zero.

Traversing an Array

To traverse an array means to move through each element in the array, one at a time. It simply means, you will visit each element at every index in the array. The most common way to perform a traversal is to start with the first index and end with the last index. However, you are not required to start at the beginning. You could traverse the array from the last index to the first index and you could traverse all of the even indices and then all of the odd indices or vice versa.

Traversals are common accomplished using a for-each loop. The enhanced for-loop will access every element in an array, starting with index [0], without replacing or removing any elements. For example:

for each loop example

Using the for-each loop, you only have access to the elements in the array, not the index. The data type of the temp variable must be the same as the data type of the array.

Assignment: Arrays Worksheet

Directions: Complete the multiple choice Arrays worksheet in itsLearning. You should trace through the problems to determine the correct answer. Code tracing is important and will help you be successful on the AP Exam.

Assignment: Numbers Lab

Directions: Design and implement an application that reads a number of integers that are in the range 0 to 50 inclusive and counts how many times each one is entered. Paste the code below into BlueJ to get started. After all input has been processed, print all of the values, with the number of times each one was entered. Submit a screenshot of your code working and paste your code in the textbox below.

Fibonacci

Assignment: FL Swap

Directions: Write a method that takes an array of integers as a parameter and swaps the first element with the last element. Post the code into the itsLearning textbox (do not attach) labeled FL Swap.

Lab: Reversing an Array

Directions: Write a program that prompts the user for an integer, then asks the user to enter that many values. Store these values in an array and print the array. Then reverse the array elements so that the first element becomes the last element, the second element becomes the second to last element, and so on, with the old last element now first. Do not just reverse the order in which they are printed; actually change the way they are stored in the array. Do not create a second array; just rearrange the elements within the array you have. (Hint: Swap elements that need to change places.) When the elements have been reversed, print the array again.

Follow your teacher's instructions for submitting the code of the lab as well as a screenshot from BlueJ.

Need help? Watch this video for the concept of reversing an array (note: the code in the video is not Java but rather a basic pseudocode).


Arrays of Objects

Arrays can store references to objects. Fairly complication information management structures can be created using only arrays and other objects. When we store objects in an array, each element is a separate object (actually it is an array of object references.)


Searching

Now that we are familiar with arrays, we need to be able to search for elements within them.

Imagine that we have to look up Joe Doe's phone number in an old fashion phonebook. You can't ask Google, Siri, or Alexa. The phone book is written in alphabetical order. What method will you use to get to the D section?

There are two ways to search, sequentially or using a binary search. Most people use something similar to the binary search method or some combination of the two.

Sequential Search

The sequential, or linear, search method is when you start at the beginning and look through every element one at a time until you reach the element you are looking for. In our phonebook example, a sequential search would mean we start at the beginning with the letter A and flip through one page at a time until we reach Doe. This is not a very efficient method for searching in a phonebook.

The best case scenario for a sequential search is that the element that we are looking for is at the beginning. The worst case scenario is that the element we are looking for is the last element. This is an effective search if the elements are not sorted. Imagine a phonebook that was not printed alphabetically. How would you find Doe if all the names were randomly printed?

Think about playing a guessing game. I am thinking of a number between 1 - 10. Using a sequential search, your guesses would be 1, 2, 3, ... until you reached my number.

Binary Search

I am thinking of a number between 1 - 10. To guess efficiently, your first guess should be 5. I will then tell you if your guess is too high or too low and you will continue from there. How many guesses will it take to reach my number? Odds are, this method of searching will be faster than the sequential search.

A binary search is when you look at the element in the middle and check to see if the element you are looking for is higher or lower (before or after). If this element is greater than the one we are looking for, we use first half of the array. Then use this approach again. If it is less than the element we want, use the second half of the array. This type of search requires your data to be sorted. This is a divide and conquer method!

In our phonebook search, trying to find Doe, you would open the phonebook in the middle and hopefully land close to the D section. This has gotten you much closer to what you am looking for on your first guess.


Two-Dimensional Arrays

The two-dimensional (2-D) array is a data-structure that is an array of arrays and simulates a rectangular grid with coordinates for each location based on the row and column. Two-dimensional arrays allow us to store data in a matrix or grid format, instead of the data just being linear as with arrays or ArrayLists. Technically, it is an array of arrays. It can store any kind of data in its slots; however, each piece of data has to be the same data type.

A 2-D array object can be created using the keyword new. Every cell in the 2-D array is filled with the default value for its data type.

General Form for creating a 2-D Array Using the Keyword new

dataType[][] nameOfArray = new dataType[numberOfRows] [numberOfColumns];

Traversing a 2-D Array in Row-Major Order

Traversing a 2-D array means to visit each and every cell in the grid. This can be done in many different ways, but for the AP Exam, you need to know two specific ways:

Assignment: Secret Code

Directions: Download the SecretCode file and print it. You will need to fill in the 2D array in row-major (meaning rows come first) order and then decode the secret code. There is what appears to be a typo but it leave it. You'll know it when you get to it. Follow your teacher's instructions for submitting your Secret Code assignment.

magic

Assignment: Magic Squares Lab

Directions: Download the Magic Squares lab. One interesting application of two-dimensional arrays is magic squares. A magic square is a square matrix in which the sum of every row, every column, and both diagonals is the same. Magic squares have been studied for many years, and there are some particularly famous magic squares. In this exercise you will write code to determine whether a square is magic.

File Square.java contains the shell for a class that represents a square matrix. It contains headers for a constructor that gives the size of the square and methods to read values into the square, print the square, find the sum of a given row, find the sum of a given column, find the sum of the main (or other) diagonal, and determine whether the square is magic. The read method is given for you; you will need to write the others. Note that the read method takes a Scanner object as a parameter.

File SquareTest.java contains the shell for a program that reads input for squares from a file named magicData and tells whether each is a magic square. Following the comments, fill in the remaining code. Note that the main method reads the size of a square, then after constructing the square of that size, it calls the readSquare method to read the square in. The readSquare method must be sent the Scanner object as a parameter.

You should find that the first, second, and third squares in the input are magic, and that the rest (fourth through seventh) are not. Note that the -1 at the bottom tells the test program to stop reading.

Follow your teacher's instructions for submitting the code of the lab as well as a screenshot from BlueJ.

Assignment: Array Quiz

Directions: Complete the Array Quiz in itsLearning.


The ArrayList Class

An ArrayList is a data structure that can store a list of objects from the same class. An ArrayList is very similar to an array, however, it can only collect object unlike arrays that can also hold primitive data. A great advantage of an ArrayList is that it is resizable. They can grow or shrink as needed as objects are added to the list or removed from the list. ArrayLists also come with methods for many useful tasks.

ArrayList Methods

Assignment: ArrayList Worksheet

Directions: Complete the multiple choice ArrayList worksheet in itsLearning. You should trace through the problems to determine the correct answer. Code tracing is important and will help you be successful on the AP Exam.

shopping cart

Lab: A Shopping Cart Using the ArrayList Class

Directions: Download the A Shopping Cart Using the ArrayList Class lab. In this exercise you will implement a shopping cart using the ArrayList class. The file Item.java contains the definition of a class named Item that models an item one would purchase. An item has a name, price, and quantity (the quantity purchased). The file Shop.java is an incomplete program that models shopping.

Follow your teacher's instructions for submitting the code of the lab as well as a screenshot from BlueJ.

Assignment: Grading Quizzes Lab

Directions: Write a program that grades arithmetic quizzes as follows:

  1. Ask the user how many questions are in the quiz.
  2. Ask the user to enter the key (that is, the correct answers). There should be one answer for each question in the quiz, and each answer should be an integer. They can be entered on a single line, e.g., 34 7 13 100 81 3 9 10 321 12 might be the key for a 10-question quiz. You will need to store the key in an array.
  3. Ask the user to enter the answers for the quiz to be graded. As for the key, these can be entered on a single line. Again there needs to be one for each question. Note that these answers do not need to be stored; each answer can simply be compared to the key as it is entered.
  4. When the user has entered all of the answers to be graded, print the number correct and the percent correct.

When this works, add a loop so that the user can grade any number of quizzes with a single key. After the results have been printed for each quiz, ask "Grade another quiz? (y/n)."


Assignment: Unit 5 Review Worksheet

Directions: Complete the review worksheet in itsLearning to review for the unit assessment.

Assignment: Array Free Response Exercise

Directions: Download Array Free Response document and handwrite the code following the detailed instructions. You must also read the code comments provided for you as they give valuable information and instructions to help you write the class and methods required.

Review

Credits

Array Example Image: http://www.mainjava.com/java/core-java/complete-array-tutorial-in-java-with-programming-example/