Complete the ArrayList practice before reviewing the solution.
Review the ArrayList practice solution with AP CS Tutor Brandon Horn.
removeWord method
public static void removeWord(ArrayList<String> words, String wordToRemove)
{
for(int i = words.size() - 1; i >= 0; i--)
if(words.get(i).equals(wordToRemove))
words.remove(i);
}
When the element at position i is removed from an ArrayList, the elements at all subsequent positions shift one position to the left. If this is ignored, a regular for loop skips consecutive matching elements.
The example below illustrates this behavior.
words -> ["apple" "banana", "banana", "pear", "peach"]
0 1 2 3 4
wordToRemove -> "banana"
i: 1
When i is 1, "banana" is removed. The elements after position 1 shift one spot to the left. The value of i is increment.
words -> ["apple" "banana", "pear", "peach"]
0 1 2 3
wordToRemove -> "banana"
i: 2
The "banana" previously at position 2 is now at position 1. The loop moved past position 1, and skipped "banana".
One way to account for the shift is to traverse the list backwards. The elements that shift are the ones that have already been checked.
The example below illustrates the behavior.
words -> ["apple" "banana", "banana", "pear", "peach"]
0 1 2 3 4
wordToRemove -> "banana"
i: 2
When i is 2, "banana" is removed. The elements after position 2 shift one spot to the left. The value of i is decremented.
words -> ["apple" "banana", "pear", "peach"]
0 1 2 3
wordToRemove -> "banana"
i: 1
removeWord method (alternative 1)
int i = 0;
while(i < words.size())
{
if(words.get(i).equals(wordToRemove))
words.remove(i);
else
i++;
}
An alternative approach is to use a while loop that only increments i when the element at i is not removed. The loop either goes to the next element or lets the next element come to it, but not both.
removeWord method (alternative 2)
for (int i = 0; i < words.size(); i++)
{
if (words.get(i).equals(wordToRemove))
{
words.remove(i);
i--;
}
}
Another alternative is to decrement i whenever an element removes. Decrementing i cancels the increment that runs each time the for loop runs. This approach has the disadvantage of modifying the loop variable within the loop, which makes the loop less clear.
duplicateMatching method
public static void duplicateMatching(ArrayList<Integer> list, Integer elem)
{
for(int i = list.size() - 1; i >= 0; i--)
if(list.get(i).equals(elem))
list.add(i, elem);
}
duplicateMatching has an issue similar to removeWord. When an element is added at position i, the elements previously at and after position i shift one spot to the right. A regular loop that increments i each time would incorrectly find another match. This results in a loop that adds elements to the list until memory is exhausted.
With minor modifications, each alternate solution to removeWord can be applied to duplicateMatching.
removeAdjacentDuplicates method
public static void removeAdjacentDuplicates(ArrayList<Integer> list)
{
int i = 1;
while(i < list.size())
{
if(list.get(i - 1).equals(list.get(i)))
list.remove(i);
else
i++;
}
}
removeAdjacentDuplicates has an issue similar to the other 2 exercises. As with duplicateMatching, any of the 3 solutions presented for removeWord can be modified to work.
removeAdjacentDuplicates needs to check 2 elements during each loop execution, so the loop bounds need to be chosen carefully. In the example solution, i starts at 1.