Activity 10.4.1.
Set number to a different number and guess what number / and % will return. Which operator gives you a digit in number?
Section 10.4 ArrayList algorithms
All the basic loop algorithms we discussed in Section 5.3 Basic loop algorithms and again in Section 6.3 Array algorithms can also be used with an
ArrayList. For instance we can sum the elements of an ArrayList<Integer> or ArrayList<Double>. We can count the number of elements of an ArrayList<String> that start with a specific letter or that are greater than a certain length. We can search an ArrayList for an element that meets some criteria, count how many do, or test whether at least one does or whether all elements do. Likewise we can rotate elements within an ArrayList and write algorithms that operate on pairs of elemnets, either adjacent pairs or all possible pairs.
But there are a few kinds of algorithms that we can write with
ArrayLists that don’t apply to arrays since we can add and remove elemnets from ArrayLists. For instance, we can write algorithms to remove certain elements from an ArrayList or to insert new elements at specific positions into an ArrayList.
We’ll look at those algorithms in this section and also take a quick peek at algorithms that operate on more than one
ArrayList in parallel.
Subsection 10.4.1 Removing elements
Suppose we want to remove items matching some criteria from an
ArrayList. We need to check all the elements of the list so that suggests we need a loop.
But we need to be a bit careful about how we iterate through the loop since when we remove an item from a list all the items to the right (at greater indexes) shift down one index.
As we discussed in the previous section, we can’t use an enhanced
for loop because it will throw a ConcurrentModificationException if the size of the ArrayList changes while the loop is running. Also, in an enhanced for loop we don’t know what index we are on so we can’t remove the current item anyway with the remove(int) method.
So there are a few ways to implement removing elements from an
ArrayList. We can use a regular for loop and adjust the index variable when we remove an item, we can do roughly same thing with a while loop, which gives us a bit more explicit control over the index variable. Or we can loop backwards.
A normal
for does require doing a thing that is generally frowned upon, namely modifying the loop variable in the body of the loop. The problem is, if we determine that we want to remove the element at index i and call list.remove(i), then all the elements after the removed one shift down one and if we continue looping as normal, i will get incrementeed and we will not consider the element that used to be at position i + 1 and is now at position i. So we have to write something like this;
for (int i = 0; i < strings.size(); i++) {
if (dontLikeThisOne(strings.get(i))) {
strings.remove(i);
// The element that was at i + 1 is now at i,
// so on the next iteration of the loop we'd
// end up skipping that element. So we decrement
// i here so after the i++ we're back to the
// current value of i.
i--;
}
}
In the case where we remove the item, we decrement
i with i-- so that when the for loop increments it in the updater, it gets set back to the same value and the next iteration of the loop will consider the element that just shifted down into position we just removed the element from.
Since it can be a bit confusing to have the loop variable modified both by the
for loop updater clause and in the body of the loop, some programmers would prefer to implement this technique using a while loop as a way to make it clear that we doing something beyond a normal for loop.
int i = 0;
while (i < strings.size()) {
if (dontLikeThisOne(strings.get(i))) {
strings.remove(i);
} else {
i++;
}
}
Because we have to update the loop variable in the loop body anyway, in this code instead of decrementing
i to compensate for the fact it is about to be incremented, we can instead only increment it when we don’t remove the current item. Thus i always points to the position of the next element to consider for removal: if we just removed an item and things have shifted down it stays where it is and if we have considered the element at position i and kept it, then i is incremented to we can consider the next element.
The third approach is possibly the cleanest. Instead of looping forward through the loop, if we loop backwards, starting at the last index and decrementing toward 0, then we don’t have to compensate at all. When we remove an item, the items at greater indices shift down but they’ve all been considered already so we can just keep going.
for (int i = strings.size() - 1; i >= 0; i--) {
if (dontLikeThisOne(strings.get(i))) {
strings.remove(i);
}
}
This approach also has the very slight advantage over the forward loops that it doesn’t spend any time shifting down elements that will later be removed.
Subsection 10.4.2 Inserting elements
Inserting elements into an
ArrayList sometimes requires a similar attention to how shifting elements around in the ArrayList is interacts with our loop variable.
If we just want to insert one element things are pretty easy. The
add(int, E) method will insert an element at a given index. So all we have to do is figure out where we want to insert the new element and then call add with that index.
For example, suppose we wanted to write a method to insert a word into an already sorted list of words. Our basic plan might be, loop through the list until we find a word that is greater than the word we want to insert using
compareTo and insert the word at that postion. It might look like this:
public void addWord(String word, ArrayList<String> words) {
for (int i = 0; i < words.size(); i++) {
if (word.compareTo(words.get(i)) <= 0) {
words.add(i, word);
return;
}
}
words.add(word);
}
In this method as soon as the word is added we’re done and we can return so it doesn’t matter that the rest of the list has shifted down. Then outside the loop, if we get there, we add
word at the end of the list because it must belong after all the other words in the list.
Now consider a slightly different problem. Insert the word
"very" into the list before every occurrence of the word "special". Does this code work?
public void addVery(ArrayList<String> words) {
for (int i = 0; i < words.size(); i++) {
if (words.get(i).equals("special")) {
words.add(i, "very");
}
}
}
If you said it doesn’t, you are correct and probably see why. If you said it does work or weren’t sure, consider what happens the first time it comes across the word
"special". Let’s say that happens at index 10. The line words.add(i, "very") insert "very" at position 10 as we want. But now where is "special"? It has shifted up one position to index 11. But now the loop continues and i is incremented to 11. So words.get(i) returns "special" again and the code insert another "very" shifting "special" up to position 12. We are stuck in an infinite loop which will eventually crash with an OutOfMemoryError when we’ve inserted more very’s than we have room to store in our computers memory.
The fix to this is similar to the fix we used when removing elements. We can adjust the index like this:
public void addVery(ArrayList<String> words) {
for (int i = 0; i < words.size(); i++) {
if (words.get(i).equals("special")) {
words.add(i, "very");
i++; // add an extra 1
}
}
}
Or we could use the trick of looping backwards since then after inserting the
"very" and shifting up the "special", we’ll move down to the word that used to be before "special" and carry on, eventually getting to index 0.
public void addVery(ArrayList<String> words) {
for (int i = words.size() - 1; i >= 0; i--) {
if (words.get(i).equals("special")) {
words.add(i, "very");
}
}
}
Subsection 10.4.3 Collecting into an ArrayList
One variant of the standard loop algorithms that works well with
ArrayLists is an accumulating loop. Previously we have written loops that accumulate numbers by counting or totalling them or accumulate into a String by adding to String variable in a loop.
But an
ArrayList is an excellent data structure to use for accumulating values since we can add elements to it whenever we want. For instance, suppose we had a ArrayList<String> containing a bunch of words and we wanted to count how many were longer than six letters. That’s a straightforward counting loop:
int count = 0;
for (String word : words) {
if (word.length() > 6) {
count++;
}
}
In that code, the variable
count is our accumulator and it is accumulating a count. But now with an ArrayList we colud instead collect all the words longer than six letters.
ArrayList<String> longWords = new ArrayList<>();
for (String word : words) {
if (word.length() > 6) {
longWords.add(word);
}
}
That is an example of a filtering pattern because it filters the original list down to a new list containing only the ones that meet a certain criteria.
Another related pattern is mapping where we make a new list containing an element for every element of the original list but transformed in some way. For instance this loop makes a list of all-uppercase version of all the words in
words.
ArrayList<String> loudWords = new ArrayList<>();
for (String word : words) {
loudWords.add(word.toUpperCase());
}
Subsection 10.4.4 Coding Challenge: FRQ Digits
This coding challenge is based on the 2017 Free Response Question part 1a on the 2017 AP CSA exam. In this question, you are asked to write a constructor for a class called
Digits. This constructor takes an integer number as its argument and divides it up into its digits and puts the digits into an ArrayList. For example, new Digits(154) creates an ArrayList with the digits [1, 5, 4].
First, let’s discuss how to break up a number into its digits. Try the code below. What happens if you divide an integer by 10? Remember that in integer division the result truncates (cuts off) everything to the right of the decimal point. Which digit can you get by using
% 10 which returns the remainder after dividing by 10? Try a different number and guess what it will print and then run to check.
We can use a while loop to print out each digit in reverse order starting from the right (4, 5, 1 for the number 154) while dividing it by 10. You can try it in the active code above. Here is the pseudocode:
-
while number is greater than 0
Now, let’s write a constructor for the
Digits class that uses this loop and adds each found digit to the ArrayList instead of printing it out.
Note that this will create the digit list in reverse order. To get the digits in the right order, you can use the
add(index, obj) method to add the digit to the beginning of the ArrayList instead of the end.
Project 10.4.2.
Complete the challenge below to put the digits of a number in an ArrayList.
Subsection 10.4.5 Parallel lists
Some algorithms require multiple
ArrayList objects to be traversed simultaneously. For example, the following code traverses three parallel ArrayLists, one that holds a list of student names, and the other two hold the students’ scores on two tests. It prints the names of all the students who did better on Test 2 than on Test 1.
ArrayList<String> students = studentNames();
ArrayList<Integer> test1 = getTestScores("Test 1");
ArrayList<Integer> test2 = getTestScores("Test 2");
for (int i = 0; i < students.size(); i++) {
if (test2.get(i) > test1.get(i)) {
System.out.println(students.get(i));
}
}
The key to this kind of algorithm is that the lists need to be organized the same way; they need to each be the same length and also in the same order. That is, for every index
i the scores at index i in test1 and test2 have to belong to the student at index i in students.
Subsection 10.4.6 Summary
-
(AP 4.10.A.1) There are standard
ArrayListalgorithms that utilize traversals to:-
determine a minimum or maximum value
-
compute a sum or average
-
determine if at least one element has a particular property
-
determine if all elements have a particular property
-
determine the number of elements having a particular property
-
access all consecutive pairs of elements
-
determine the presence or absence of duplicate elements
-
shift or rotate elements left or right
-
reverse the order of the elements
-
insert elements
-
delete elements
-
-
(AP 4.10.A.2) Some algorithms require multiple String, array, or ArrayList objects to be traversed simultaneously.
You have attempted of activities on this page.
