UNIT 7

ArrayList

IN THIS UNIT

Summary: In this unit we will discuss the ArrayList, along with some of the methods that are used to access and manipulate its elements. In addition to the array algorithms that were introduced in the previous unit (which can also be done with ArrayLists), we will look at searching and sorting algorithms that you need to know for the AP Computer Science A Exam.

Images

Key Ideas

image An ArrayList is a data structure that can store a list of objects from the same class.

image An ArrayList resizes itself as objects are added to and removed from the list.

image To traverse a data structure means to visit each element in the structure.

image The enhanced for loop (for-each loop) is a special looping structure that can be used by either arrays or ArrayLists.

image The copy algorithm makes a duplicate of a data structure.

image The accumulate algorithm traverses a list, adding each value to a total.

image The find-highest algorithm traverses and compares each value in the list to determine which one is the largest.

image The process of developing an original algorithm requires concentration and analytical thought.

image Accessing data that is buried within a class hierarchy requires the programmer to use the methods that belong to the class.

image The sequential search algorithm finds a value in a list.

image The Insertion Sort, Selection Sort, and Merge Sort are sorting routines.

The ArrayList

Definition of an ArrayList

An ArrayList is a complex data structure that allows you to add or remove objects from a list and it changes size automatically.

Declaring an ArrayList Object

An ArrayList is an object of the ArrayList class. Therefore, to create an ArrayList, you need to use the keyword new along with the constructor from the ArrayList class. You also need to know the data type of the objects that will be stored in the list. The ArrayList uses a pair of angle brackets, < and >, to enclose the class name of the objects it will store.

Using a raw ArrayList (without <>) allows the user to store a different data type in each position of the ArrayList, which is not typically done since Java 5.0 arrived in 2004. The ArrayList <E> notation is preferred over ArrayList because it allows the compiler to find errors that would otherwise be found at run-time. You might see some older AP Computer Science A Exam questions using this syntax.

The graphic that follows is a visual representation of what the ArrayList looks like in memory.

Example

Declare an ArrayList of Circle objects. Please note that I am referring back to the Circle class from Unit 5 and that the memory address is simulated.

Images

Images

An ArrayList Always Starts Out Empty

When you create an ArrayList object, it is empty, meaning that there are no items in the list. It’s like when your mom starts to make a “To Do” list and she writes the words “To Do” on the top of a piece of paper. The list is created but there is nothing in the list.

Example

Images

An ArrayList Is Resizable

When your mom writes, “Go grocery shopping” or “Buy awesome video game for favorite child” on her To Do list, the size of the list grows. As she completes a task on the list, she crosses it out and the size of the list shrinks. This is exactly how an ArrayList is resized.

Automatic Resizing

An awesome feature of the ArrayList is its ability to resize itself as elements are added to or removed from the list. The size() method (explained later) immediately recalculates how many elements are in the list.

An ArrayList Requires an import Statement

The ArrayList is not part of the built-in Java language package, so you have to let the compiler know that you plan on creating an ArrayList by putting an import statement prior to the class declaration.

Images

You will not need to write any import statements on the AP exam.

An ArrayList Can Only Store Objects

Unlike the array, which could store primitive variables like an int or double, as well as objects, the ArrayList can only store objects. If you want to store an int or double in an ArrayList, you must use the Integer or Double wrapper classes. This is one of the reasons why the wrapper classes were created (back in Unit 2 they were introduced).

Example

Create an ArrayList of Integers. Add an int to the ArrayList and secretly watch as the int is automatically converted to an integer using a secret, Java black box technique called autoboxing (also introduced back in Unit 2).

Images

Important ArrayList Methods

The ArrayList class comes with a large array of methods (see my pun). These methods make it easy to work with the objects inside the ArrayList. The AP Computer Science A Exam does not require you to know all of the methods from the ArrayList class; however, it does require you to know a subset of them.

The add Method

There are two add methods for the ArrayList. The add(E object) method appends the object to the end of the list. This means that it adds the object to the end of the list. It also returns the value true. The size of the ArrayList is automatically updated to reflect the addition of the new element.

What’s with E?

The data type E is known as a generic type. It simply means that you can put any kind of data type here. I like to say, “The method takes Every kind of data type.”

Example

Create an ArrayList of Circle objects. Add three Circle objects to the ArrayList where the first has a radius of 8, the second doesn’t provide a radius so the radius gets the default value of 0, and finally, the last circle has a radius of 6.5. Note: This example will be used in the explanations for the other ArrayList methods.

Images

After line 1 is executed: There is one Circle object in the ArrayList.

Images

After line 2 is executed: There are two Circle objects in the ArrayList.

Images

After line 3 is executed: There are three Circle objects in the ArrayList.

Images

Another add Method

The add(int index, E object) method inserts the object into the position index in the ArrayList, shifting the object that was previously at position index and each of the objects after it over one index. The index for each of the objects affected by the add is incremented. The method does not return a value.

An ArrayList Is Like the Lunch Line at School

An ArrayList can be visualized like the lunch line at school. Imagine there are 10 students in line and they are numbered 0 through 9. Person 0 is the first person in line.

Suppose the unthinkable happens and a student walks up and cuts the line. They have just inserted themselves into the list. If the cutter is now the third person in line, then they have just performed an add(2, "cutter"). This action impacts everyone who is in line after the cutter. The person who used to be in position 2, is now in position 3. The person who used to be at position 3 is now in position 4, and so on. The index for each person behind the cutter was incremented by one.

Images

After line 4 is executed: The Circle object with a radius of 4 was inserted into the position with an index of 1 (the second position). All of the Circle objects after it had to move over one slot.

Images

The size Method

The size() method returns the number of elements in the ArrayList. Notice that this is different from the length field of the array, which tells you how many slots were set aside and not the actual number of valid items stored in the array.

Images

Images

Images

As in the 1D array and the 2D array, you will get an error if you try to access objects outside of the range of the list. The error when doing this with an ArrayList is called the IndexOutOfBoundsException.

Images

The index, 88, is not in the range of 0 ≤ index ≤ myCircle.size().

The remove Method

The remove(int index) method deletes the object from the list that is at index. Each of the objects after this shifts down one index. The method also returns a reference to the object that was removed from the list.

Images

After line 6 is executed: the Circle object that used to be in the slot at index 2 is removed (the circle with a radius of 0). The Circle objects that were positioned after it all move down one slot and someCircle now points to the Circle object that was removed.

Images

The get Method

The get(int index) method returns the object that is located in the ArrayList at position index. It doesn’t remove the object; it just returns a copy of the object reference. This way, an alias is created (more than one object reference pointing to the same object). The value of index must be greater than or equal to zero and less than the size of the ArrayList.

Example

Get the Circle object at index 2 and assign it to a different Circle reference variable:

Images

The set Method

The set(int index, E object) method replaces the object in the ArrayList at position index with object. It returns a reference to the object that was previously at index.

Example

Replace the Circle object at index 0 with a new Circle object with a radius of 20:

Images

Images

image

Images

To find the number of slots in an array, use the length field.

To find the number of objects in an ArrayList, use the size() method.

To find the number of characters in a string, use the length() method.

Traversing an ArrayList Using a for Loop

Traversing is a way of accessing each element in an array or ArrayList through the use of iteration. The following code uses a for loop to print the area of each of the Circle objects in the ArrayList. The get method is used to retrieve each Circle object and then the getArea method is used on each of these Circle objects.

Images

Images

Traversing an ArrayList Using the Enhanced for Loop

The enhanced for loop (for-each loop) can be used with an ArrayList. The following code prints the area of each of the Circle objects in the ArrayList. Notice that the temporary variable, element, is the same data type as the objects in the ArrayList. In contrast to the general for loop shown above, the enhanced for loop does not use a loop control variable. Therefore, there is no need for the get(i) method since the variable circle is a copy of each of the Circle objects, one at a time and the getArea method can be used directly with circle.

Images

Images

Printing the Contents of an ArrayList

Unlike an array, the contents of an ArrayList can be displayed to the console by printing the reference variable. The contents are enclosed in brackets and separated by commas.

Images

Note: If you want to format the output when printing the contents of an ArrayList, you should traverse the ArrayList.

Images

Do Not Use remove() in the Enhanced for Loop

Deleting elements during a traversal requires special techniques to avoid skipping elements. Never use the enhanced for loop (for-each) loop to remove an item from an ArrayList. You need the index to perform this process and the for-each loop doesn’t use one. However, if you have to perform a remove, use an index variable with a while loop. Increment the index to get to the next element in the ArrayList. But, if you perform a remove, then don’t increment the index.

Images

Avoid Run-time Exceptions

Since the indices for an ArrayList start at 0 and end at the number of elements - 1, accessing an index value outside of this range will result in an ArrayIndexOutOfBoundsException being thrown.

Changing the size of an ArrayList while traversing it using an enhanced for loop can result in a ConcurrentModifcationException being thrown. Therefore, when using an enhanced for loop to traverse an ArrayList, you should not add or remove elements.

Images

You will receive a Java Quick Reference sheet to use on the multiple-choice and free-response sections which lists the ArrayList class methods that may be included on the exam. Make sure you are familiar with it before you take the exam.

The Copy Algorithm for the ArrayList

Making a copy of an ArrayList means to create a brand-new object that is a duplicate of the original. This is different from creating a new ArrayList variable that references the original ArrayList. 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)

Images

Java Code 1: Using an ArrayList (for loop)

Images

Java Code 2: Using an ArrayList (for-each loop)

Images

The Sequential (or Linear) Search Algorithm

When you search iTunes for a song, how does it actually find what you are looking for? It may use a sequential search to find the name of a song. A sequential (or linear) search is the process of looking at each of the elements in a list, one at a time, until you find what you are looking for. Sequential (or linear) search is one standard algorithm for searching. Another search algorithm, the binary search, will be discussed in Unit 10.

Images

The Search Target

When you search for a specific item in a list, the item you are looking for is often referred to as the search target. If the target is not found, a value of -1 is often returned.

Solution 1: Look at every item in the list.

Algorithm 1:

Step 1: Create a variable called foundIndex and set it equal to -1

Step 2: Look at each of the titles in the array one at a time

Step 3: Compare each title to the target title

Step 4: If the title is equal to the target title, then assign foundIndex to value of the current index

Step 5: Continue looking until you reach the end of the list

Step 6: Return the value of foundIndex

Pseudocode 1:

Images

Java Code 1: Using an ArrayList

Images

Images

Java Code 2: Using an array

Images

Did you notice that neither of the examples used a for-each loop? That was on purpose. Remember, if you need to access the index of an element in an array or ArrayList, then a for-each loop cannot be used.

Solution 2: Stop looking if you find the search target.

Algorithm 2:

Step 1: Look at each of the titles in the array one at a time

Step 2: Compare the target title to each of the titles

Step 3: If the title is equal to the target title, then stop looking and return the current index

Step 4: Continue looking until you reach the end of the list

Step 5: Return -1

Pseudocode 2:

Images

Java Code 3: Using an ArrayList

Images

Java Code 4: Using an array

Images

Efficiency

Analyze the two solutions that searched for the title of a song.

The second algorithm is more efficient than the first because the method stops looking for the title as soon as it finds it. The first algorithm is less efficient than the second because it continues to compare each of the titles in the list against the search target even though it may have already found the search target.

Efficiency

An efficient algorithm does its job in the fastest way it can. Efficient programs are optimized to reduce CPU (central processing unit) time and memory usage.

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?

General Problem: Add up all of the hits for a baseball team.

Refined Problem: Write a method that finds the sum of all of the hits in an array of hits.

Final Problem: Write a method called findSum that has one parameter: an ArrayList of Integers. The method should return the sum of all of the elements in the array.

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:

Images

Java code 1: Using an ArrayList (for-each loop)

Images

Java code 2: Using an ArrayList (for loop)

Images

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:

Images

Java code 1: Using an ArrayList (for-each loop)

Images

Java code 2: Using an ArrayList (for loop)

Images

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.

Images

Likewise, to solve the find-lowest problem, you could set the low to be a really, really big number.

Images

Images

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

The Accumulate Advanced Algorithm

You have been hired by the high school baseball team to write a program that calculates statistics for the players on the team. You decide to have a class called BaseballPlayer. Every BaseballPlayer has a name, a numberOfHits, and a numberOfAtBats. The BaseballRunner has an array of BaseballPlayer objects called roster. Your goal is to find the team batting average.

Images

Images

Algorithm:

Step 1: Create a variable called totalHits and set it equal to 0

Step 2: Create a variable called totalAtBats and set it equal to 0

Step 3: Look at each player on the roster

Step 4: Get the number of hits for the player and add it to totalHits

Step 5: Get the number of atBats for the player and add it to totalAtBats

Step 6: Continue until you reach the end of the list

Step 7: Compute the teamBattingAverage by dividing the totalHits by the totalAtBats

Step 8: Return the teamBattingAverage

Pseudocode:

Images

Java Code 1: Java code using an array (for loop)

Images

Java Code 2: Java code using an array (for-each loop)

Images

Java Code 3: Java code using an ArrayList (for loop)

Images

Java Code 4: Java code using an ArrayList (for-each loop)

Images

Images

Images

The Find-Highest Advanced Algorithm

Algorithm:

Step 1: Create a variable called highestAverage and assign it a really small number

Step 2: Create a variable called bestPlayer and assign it the empty string

Step 3: Look at each of the players in the roster

Step 4: If the batting average of the player is greater than highestAverage, then set the highestAverage to be that player’s average and set bestPlayer to be the name of the player

Step 5: Continue until you reach the end of the list

Step 6: Return the name of bestPlayer

Pseudocode:

Images

Java Code 1: Java code using an array (for loop)

Images

Images

Java Code 2: Java code using an array (for-each loop)

Images

Java Code 3: Java code using an ArrayList (for loop)

Images

Java Code 4: Java code using an ArrayList (for-each loop)

Images

Images

Images

The Twitter-Sentiment-Analysis Advanced Algorithm

Twitter has become very popular and Twitter Sentiment Analysis has grown in popularity. The idea behind Twitter Sentiment is to pull emotions and/or draw conclusions from the tweets. A large collections of tweets can be used to make general conclusions of how people feel about something. The important words in the tweet are analyzed against a library of words to give a tweet a sentiment score.

One of the first steps in processing a tweet is to remove all of the words that don’t add any real value to the tweet. These words are called stop words, and this step is typically part of a phase called preprocessing. For this problem, your job is to remove all the stop words from the tweet. There are many different ways to find meaningless words, but for our example, the stop words will be all words that are three characters long or less.

Solution 1: Using an ArrayList

Algorithm 1:

Step 1: Create a list called longWords

Step 2: Look at each word in the original list

Step 3: If the word is greater than three characters, add that word to longWords

Step 4: Continue until you reach the end of the original list

Step 5: Return longWords

Pseudocode 1:

create a list called longWords

Images

Java Code 1: Using an ArrayList (for-each loop)

Images

Solution 2: Using an Array

This solution requires more work than the ArrayList solution. Since we don’t know how big to make the array, we need to count how many words are greater than three characters before creating it.

Algorithm 2:

Step 1: Create a counter and set it to zero

Step 2: Look at each word in the original list

Step 3: If the length of the word is greater than three characters, add one to the counter

Step 4: Continue until you reach the end of the list

Step 5: Create an array called longWords that has a length of counter

Step 6: Create a variable that will be used as an index for longWords and set it to zero

Step 7: Look at each word in the original list

Step 8: If the length of the word is greater than three characters, add the word to longWords and also add one to the index that is used for longWords

Step 9: Continue until you reach the end of the list

Step 10: Return the longWords array

Pseudocode 2:

set counter = 0

Images

create an array called longWords whose length is the same as counter

set index = 0

Images

Java Code 2: Using an array (using a for-each loop and a for loop)

Images

Images

Background on Sorting Data

The idea of sorting is quite easy for humans to understand. In contrast, teaching a computer to sort items all by itself can be a challenge. Through the years, hundreds of sorting algorithms have been developed, and they have all been critiqued for their efficiency and memory usage. The AP Computer Science A Exam expects you to be able to read and analyze code that uses three main sorts: the Insertion Sort, the Selection Sort, and the Merge Sort (to be discussed in Unit 10).

The most important thing to remember is different sorting algorithms are good for different things. Some are easy to code, some use the CPU efficiently, some use memory efficiently, some are good at adding an element to a pre-sorted list, some don’t care whether the list is pre-sorted or not, and so on. Of our three algorithms, Merge Sort is the fastest, but it uses the most memory.

The Swap Algorithm

Recall the swapping algorithm that you learned in Unit 6: Array. It is used in some of the sorting algorithms in this concept.

Images

Sorting Algorithms on the AP Computer Science A Exam

You will not have to write the full code for any of the sorting routines described in this unit in the Free-Response Section. You should, however, understand how each works because they might appear in the Multiple-Choice Section.

Insertion Sort

The Insertion Sort algorithm is similar to the natural way that people sort a list of numbers if they are given the numbers one at a time. For example, if you gave a person a series of number cards one at a time, the person could easily sort the numbers “on the fly” by inserting the card where it belonged as soon as the card was received. Insertion Sort is considered to be a relatively simple sort and works best on very small data sets.

To write the code that can automate this process on a list of numbers requires an algorithm that does a lot of comparing. Let’s do an example of how Insertion Sort sorts a list of numbers from smallest to largest.

Images

This algorithm uses a temporary variable that I will call temp. The first step is to put the number that is in the second position into the temporary variable (temp). Compare temp with the number in the first position. If temp is less than the number in the first position, then move the number that is in the first position to the second position and put temp in the first position. Now, the first pass is completed and the first two numbers are sorted from smallest to largest.

Next, put the number in the third position in temp. Compare temp to the number in the second position in the list. If temp is less than the second number, move the second number into the third position and compare temp to the number in the first position. If temp is less than the number in the first position, move the number in the first position to the second position, and move temp to the first position. Now, the second pass is completed and the first three numbers in the list are sorted. Continue this process until the last number is compared against all of the other numbers and inserted where it belongs.

I’ll Pass

A pass in programming is one iteration of a process. Each of these sorts makes a series of passes before it completes the sort. An efficient algorithm uses the smallest number of passes that it can.

Implementation

The following class contains a method that sorts an array of integers from smallest to greatest using the Insertion Sort algorithm. Note, an ArrayList could have also been used.

Images

Images

Selection Sort

The Selection Sort algorithm forms a sorted list by repeatedly finding and selecting the smallest item in a list and putting it in its proper place.

Images

To sort a list of numbers from smallest to largest using Selection Sort, search the entire list for the smallest item, select it, and swap it with the first item in the list (the two numbers change positions). This completes the first pass. Next, search for the smallest item in the remaining list (not including the first item), select it, and swap it with the item in the second position. This completes the second pass. Then, search for the smallest item in the remaining list (not including the first or second items), select it, and swap it with the item in the third position. Repeat this process until the last item in the list becomes (automatically) the largest item in the list.

Implementation

The following class contains a method that sorts an array of integers from smallest to greatest using the Selection Sort algorithm. Note, an ArrayList could have also been used.

Images

Images

Images

Rapid Review

The ArrayList

•   The ArrayList is a complex data structure that can store a list of objects.

•   The two general forms for declaring an ArrayList are:

Images

•   An ArrayList can only hold a list of objects; it cannot hold a list of primitive data.

•   Use the Integer or Double classes to make an ArrayList of int or double values.

•   The initial size of an ArrayList is 0.

•   The add(E object) method appends the object to the end of the ArrayList. It also returns true.

•   To append means to add on to the end of a list.

•   The add(int index, E object) method inserts object at position index (Note: index must be in the interval: [0,size]). As a result of this insertion, the elements at position index and higher move 1 index farther from the 0 index.

•   The get(int index) method returns a reference to the object that is at index.

•   The set(int index, E object) method replaces the element at position index with object and returns the element that was formerly at index.

•   The remove(int index) method removes the element at position index, and subsequently subtracts one from the indices of the elements at positions index + 1 and greater. It also returns the element that was removed.

•   The size() method returns an int that represents the number of elements that are currently in the ArrayList.

•   The size of the ArrayList grows and shrinks by either adding or removing elements.

•   The size() method adjusts accordingly as elements are added or removed.

•   Using an index that is not in the range of the ArrayList will throw an IndexOutOfBoundsException.

•   The ArrayList requires an import statement since it is not in the standard library, but this will never be required on the AP exam.

Traversing an ArrayList

•   To traverse an ArrayList means to visit each of the elements in the list.

•   There are many ways to traverse an ArrayList, but the most common way is to start at the beginning and work toward the end.

•   If a for loop is used to traverse an ArrayList, then the get() method will be required to gain access to each of the elements in the ArrayList.

•   If an enhanced for loop is used to traverse an ArrayList, then the get() method is not required to gain access to each of the elements in the ArrayList, since each object is automatically retrieved by the loop, one at a time.

•   If you need to remove elements from an ArrayList, you may consider starting at the end of the list and working toward the beginning.

Algorithms and Pseudocode

•   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 is 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.

•   The process of developing an original algorithm requires concentration and analytical thought.

•   Accessing data buried within a class hierarchy requires the programmer to use the methods that belong to the class.

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.

Sequential Search Algorithm

•   The sequential search algorithm searches a list to find a search target.

•   It looks at each element in the list one at a time comparing the element to the search target.

•   If the element is not found, -1 is usually returned.

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.

Insertion Sort

•   Insertion Sort uses an algorithm that repeatedly compares the next number in the list to the previously sorted numbers in the list and inserts it where it belongs.

Selection Sort

•   Selection Sort uses an algorithm that repeatedly selects the smallest number in a list and swaps it with the current element in the list.

Review Questions

Basic Level

1.   Assume that cities is an ArrayList<String> that has been correctly constructed and populated with the following items.

Images

Consider the following code segment.

Images

What items does cities contain after executing the code segment?

(A) ["Cleveland", "Detroit", "Oakland", "Chicago", "Seattle", "Denver", "Boston"]

(B) ["Oakland", "Milwaukee", "Seattle", "Boston", "Detroit", "Cleveland"]

(C) ["Oakland", "Chicago", "Seattle", "Boston", "Detroit", "Cleveland"]

(D) ["Oakland", "Milwaukee", "Denver", "Boston", "Detroit", "Cleveland"]

(E) ["Oakland", "Chicago", "Seattle", "Denver", "Detroit", "Cleveland"]

2.   Consider the following code segment.

Images

What is printed as a result of executing the code segment?

(A) [French, English, Math, Biology]

(B) [French, Art, Biology]

(C) [French, English, Art, Math, Biology]

(D) [French, Math, Biology]

(E) IndexOutOfBoundsException

Questions 3-6 refer to the following information.

Array arr has been defined and initialized as follows

Images

3.   Which of the following shows the elements of the array in the correct order after the first pass through the outer loop of the Insertion Sort algorithm?

(A) 1 5 3 8 6 4 2 7

(B) 1 3 8 5 6 4 2 7

(C) 5 3 7 1 6 4 2 8

(D) 3 5 8 1 6 4 2 7

(E) 1 2 3 4 5 6 7 8

4.   Which of the following shows the elements of the array in the correct order after the fourth pass through the outer loop of the Insertion Sort algorithm?

(A) 1 3 5 6 8 4 2 7

(B) 1 2 3 4 6 5 8 7

(C) 1 2 3 4 5 6 7 8

(D) 3 5 8 1 6 4 2 7

(E) 1 2 3 4 5 6 8 7

5.   Which of the following shows the elements of the array in the correct order after the first pass through the outer loop of the Selection Sort algorithm?

(A) 1 2 3 5 6 4 8 7

(B) 1 3 8 5 6 4 2 7

(C) 1 3 5 8 6 4 2 7

(D) 1 5 3 8 6 4 2 7

(E) 5 3 1 6 4 2 7 8

6.   Which of the following shows the elements of the array in the correct order after the fourth pass through the outer loop of the Selection Sort algorithm?

(A) 3 1 4 2 5 6 7 8

(B) 3 1 4 2 5 8 6 7

(C) 1 2 3 4 5 6 7 8

(D) 1 2 3 4 5 8 6 7

(E) 1 2 3 4 6 5 8 7

Advanced Level

7.   Consider the following code segment.

Images

What is printed as a result of executing the code segment?

(A) 34

(B) 37

(C) 46

(D) 47

(E) 49

8.   Assume that msg is an ArrayList<String> that has been correctly constructed and populated with the following items.

Images

Which code segment removes all String objects starting with a letter from the second half of the alphabet (n–z) from the ArrayList?

Precondition: all String objects will be lowercase

Postcondition: msg will contain only String objects from the first half of the alphabet (a–m)

I. Images

II. Images

III. Images

(A) I only

(B) I and II only

(C) II and III only

(D) I and III only

(E) I, II, and III

9.   Consider the following code segment that implements the Insertion Sort algorithm.

Images

Which of the following can be used to replace /* condition */ so that insertionSort will work as intended?

(A) arr[i] > key

(B) arr[j] > key

(C) arr[i + 1] > key

(D) arr[j + 1] > key

(E) arr[i - 1] > key

10.   Determine if the numbers in an ArrayList are always increasing.

Write a method that determines if the values in an ArrayList are always increasing. The method takes one parameter: an ArrayList of Integer. The method returns true if the elements in the array are continually increasing and false if the elements are not continually increasing.

Images

The ArrayList passed to the method:

Images

Images

Images

11.   Determine if the rate is increasing.

If a stock price is increasing, that means the value of it is going up. If the rate that the stock price is increasing is increasing, it means that the price is rising at a faster rate than it was the day before. Write a method that determines if the rate at which a stock price increases is increasing. The method has one parameter: an ArrayList of Double values that represent the stock prices. Return true if the rate that the stock is increasing is increasing, and false if the rate is not increasing.

Images

stockPrices contains the following:

Images

Images

12.   Count the empty lockers.

A high school has a specific number of lockers so students can store their belongings. The office staff wants to know how many of the lockers are empty so they can assign these lockers to new students. Consider the following classes and complete the implementation for the countEmptyLockers method.

Images

Images

Answers and Explanations

Bullets mark each step in the process of arriving at the correct solution.

1.   The answer is E.

•   Let’s picture the contents of our ArrayList in a table:

Images

•   After the remove at index 2, we have this (notice how the indices have changed):

Images

•   After adding Detroit, we have:

Images

•   After the remove at index 4, we have:

Images

•   And then we add Cleveland:

Images

2.   The answer is E.

•   Let’s make tables to represent what happens as each statement is executed.

Images

Images

Images

Images

Images

Images

Images

Images

Images

Images

Images

Oops! Can’t do it. Trying will generate an IndexOutOfBoundsException.

3.   The answer is D.

•   Our array starts as:

Images

•   The 5 is bigger than everything to its left (which is nothing), so let it be. Our algorithm starts with the 3.

•   Take out the 3 and store it in a variable: tempKey = 3. Now we have a gap.

Images

•   Is 3 < 5? Yes, so move the 5 to the right.

Images

•   There’s nothing more to check, so pop the 3 into the open space the 5 left behind.

Images

•   That’s the order after the first pass through the loop (question 3).

4.   The answer is A.

•   We start where we left off at the end of question 3.

Images

•   Now for the second pass. The 3 and 5 are in order; tempKey = 8, leaving a gap.

Images

•   Since 5 < 8, we put the 8 back into its original spot.

Images

•   Now for the third pass: 3, 5, 8 are sorted; tempKey = 1, leaving a gap.

Images

•   1 < 8, move 8 into the space 1 left behind. 1 < 5, move 5 over. 1 < 3, move 3 over, and put 1 in the first spot.

Images

•   Now for the fourth pass: 1, 3, 5, 8 are sorted; tempKey = 6, leaving a gap.

Images

•   6 < 8, move the 8 into the space 6 left behind. 5 < 6, so we’ve found the spot for 6 and we pop it in.

Images

•   Giving us the answer to question 4.

•   Note: One thing to look for in the answers when trying to recognize Insertion Sort—the end of the array doesn’t change until it is ready to be sorted. So the 4 2 7 in our example are in the same order that they were in at the beginning.

5.   The answer is B.

•   Our array starts as:

Images

•   We scan the array to find the smallest element: 1.

•   Now swap the 1 and the 5.

Images

•   That’s the order after the first pass through the loop (question 5).

6.   The answer is E.

•   We start where we left off at the end of question 5.

•   Now for the second pass. Leave the 1 alone and scan for the smallest remaining item:

Images

•   The 3 is in the spot the 2 needs to go into, so swap the 3 and the 2.

Images

•   The third pass swaps the 8 and the 3.

Images

•   The fourth pass swaps the 5 and the 4.

Images

•   This gives us the answer to question 6.

7.   The answer is C.

•   After the initial for loop, the contents of the ArrayList are: [10, 11, 12, 13].

•   Let’s consider what the for-each loop is doing. For each Integer (called i) in integerList

   add it to total (notice that total starts at 3).

   (total % 2 == 1) is a way of determining if a number is odd. If total is odd, subtract 1 from it.

•   Executing the for-each loop gives us:

   total = 3 + 10 = 13 . . . odd Images 12

   total = 12 + 11 = 23 . . . odd Images 22

   total = 22 + 12 = 34 . . . even!

   total = 34 + 13 = 47 . . . odd Images 46 and our final answer.

8.   The answer is C.

•   Using a loop to remove items from an ArrayList can be very tricky because when you remove an item, all the items after the removed item change indices. That’s why option I does not work. When item 3 "words" is removed, "starting" shifts over and becomes item 3, but the loop marches on to item 4 (now "with") and so "starting" is never considered and never removed.

•   Working backward through a loop works very well when removing items from an ArrayList because only items after the removed item will change indices, and you will have already looked at those items. Option II works and is the simplest solution.

•   Option III also works because it only increments the loop counter when an item is not removed. If an item is removed, the loop counter remains the same, so the item that gets shifted down ("starting" in the example above) is not skipped. Option III uses a while loop because it changes the loop index i, and it is bad programming style to mess with the loop index inside a for loop.

9.   The answer is B.

•   There are many small alterations possible when writing any algorithm. Do you go from 1 to length or from 0 to length -1, for example. This algorithm makes those kinds of alterations to the version given in the text. But in all cases, the general approach is:

   The outer loop goes through the array. Everything to the left of the outer loop index (i in this case) is sorted.

   Take the next element and put it into a temporary variable (key in this case).

   Look at the element to the left of the element you are working on. If it is larger than the element to be sorted, move it over. Keep doing that until you find an element that is smaller than the element to be sorted (this is the condition we need).

   Now you’ve found where our element needs to go. Exit inner loop and pop the element into place.

•   So the condition we are looking for reflects keep doing that until we find an element that is smaller than the element to be sorted, or, phrasing it like a while loop (“as long as” instead of “until”), keep going as long as the element we are looking at is larger than our key. In code, we want to keep going as long as arr[j] > key, so that’s our condition.

10.   Determine if the numbers in an ArrayList are always increasing.

Algorithm:

Step 1: Look at each of the scores in the list starting at the second element

Step 2: If the first score is less than or equal to the second score, then return false

Step 3: Advance to the next element and continue until you reach the end of the list

Step 4: Return true

Pseudocode:

Images

Java code:

Images

11.   Determine if the rate is increasing.

Algorithm:

Step 1: Iterate through the parameter array starting at the third element

Step 2: If (the third element minus the second element) is less than or equal to the (second element minus the first element), then return false

Step 3: Move onto the next element and go to Step 2 (and adjust the elements #s)

Step 4: If you get this far without returning, return true

Pseudocode:

Images

Java code:

Images

12.   Count the empty lockers.

Algorithm:

Step 1: Create a variable called total and set it to zero

Step 2: Look at each of the lockers in the list

Step 3: If the locker is not in use, increment the total

Step 4: Continue until you reach the end of the list

Step 5: Return the total

Pseudocode:

Images

Java Code: Java code using an array (for-each loop)

Images