Introduction
Topic 4.10 applies traversal skills to implement standard algorithms that solve common ArrayList problems. These algorithms mirror the array algorithms from Topic 4.5 but adapt to ArrayList's dynamic nature and method-based interface.
This topic is critical for the AP exam—particularly for the ArrayList free-response question (Question 3). You'll learn algorithms for finding extremes, computing statistics, checking properties, working with consecutive pairs, detecting duplicates, shifting, rotating, reversing, and modifying ArrayList structure. Additionally, we'll cover simultaneous traversal of multiple collections.
Finding Minimum and Maximum
Algorithm: Track the extreme value while traversing.
public static int findMax(ArrayList<Integer> list)
{
int max = list.get(0);
for (int i = 1; i < list.size(); i++)
{
if (list.get(i) > max)
{
max = list.get(i);
}
}
return max;
}
For objects: Find object with maximum attribute value.
public static Student findHighestGPA(ArrayList<Student> students)
{
Student best = students.get(0);
for (int i = 1; i < students.size(); i++)
{
if (students.get(i).getGPA() > best.getGPA())
{
best = students.get(i);
}
}
return best;
}
Computing Sum and Average
public static double average(ArrayList<Integer> nums)
{
int sum = 0;
for (int num : nums)
{
sum += num;
}
return (double) sum / nums.size();
}
The average formula:
Checking Properties
At Least One Element
Return true immediately when found:
public static boolean hasNegative(ArrayList<Integer> nums)
{
for (int num : nums)
{
if (num < 0)
{
return true;
}
}
return false;
}
All Elements
Return false immediately when violated:
public static boolean allPositive(ArrayList<Integer> nums)
{
for (int num : nums)
{
if (num <= 0)
{
return false;
}
}
return true;
}
Count Elements
public static int countEvens(ArrayList<Integer> nums)
{
int count = 0;
for (int num : nums)
{
if (num % 2 == 0)
{
count++;
}
}
return count;
}
Accessing Consecutive Pairs
Pattern: Loop from 0 to size() - 2 to access pairs (list.get(i), list.get(i+1)).
public static int countIncreases(ArrayList<Integer> nums)
{
int count = 0;
for (int i = 0; i < nums.size() - 1; i++)
{
if (nums.get(i + 1) > nums.get(i))
{
count++;
}
}
return count;
}
Critical: Must use size() - 1 to avoid IndexOutOfBoundsException.
Detecting Duplicates
Nested loop pattern:
public static boolean hasDuplicates(ArrayList<Integer> list)
{
for (int i = 0; i < list.size(); i++)
{
for (int j = i + 1; j < list.size(); j++)
{
if (list.get(i).equals(list.get(j)))
{
return true;
}
}
}
return false;
}
Note: Use .equals() for object comparison, not ==.
Shifting Elements
Unlike arrays, ArrayLists can actually shrink and grow.
Shift left (remove first):
public static void shiftLeft(ArrayList<Integer> list)
{
if (list.size() > 0)
{
list.remove(0);
}
}
// [10, 20, 30] becomes [20, 30]
Shift right (add at beginning):
public static void shiftRight(ArrayList<Integer> list, int value)
{
list.add(0, value);
}
// Adding 5 to [10, 20, 30] gives [5, 10, 20, 30]
Rotating Elements
Rotate left (first wraps to end):
public static void rotateLeft(ArrayList<Integer> list)
{
if (list.size() > 0)
{
int first = list.remove(0);
list.add(first);
}
}
// [10, 20, 30] becomes [20, 30, 10]
Rotate right (last wraps to start):
public static void rotateRight(ArrayList<Integer> list)
{
if (list.size() > 0)
{
int last = list.remove(list.size() - 1);
list.add(0, last);
}
}
// [10, 20, 30] becomes [30, 10, 20]
Reversing Elements
In-place reversal:
public static void reverse(ArrayList<Integer> list)
{
for (int i = 0; i < list.size() / 2; i++)
{
int temp = list.get(i);
list.set(i, list.get(list.size() - 1 - i));
list.set(list.size() - 1 - i, temp);
}
}
// [1, 2, 3, 4, 5] becomes [5, 4, 3, 2, 1]
Inserting Elements
Pattern: Adjust index after insertion to avoid infinite loops.
public static void insertZerosAfterEvens(ArrayList<Integer> list)
{
for (int i = 0; i < list.size(); i++)
{
if (list.get(i) % 2 == 0)
{
list.add(i + 1, 0);
i++; // Skip the inserted 0
}
}
}
// [2, 3, 4] becomes [2, 0, 3, 4, 0]
Deleting Elements
Use backwards traversal:
public static void removeNegatives(ArrayList<Integer> list)
{
for (int i = list.size() - 1; i >= 0; i--)
{
if (list.get(i) < 0)
{
list.remove(i);
}
}
}
Why backwards? Removing elements causes shifts. Traversing backwards means shifts only affect already-processed elements.
Simultaneous Traversals
Some algorithms require multiple String, array, or ArrayList objects to be traversed simultaneously.
Element-wise Addition
public static ArrayList<Integer> addLists(ArrayList<Integer> a,
ArrayList<Integer> b)
{
ArrayList<Integer> result = new ArrayList<Integer>();
int minSize = Math.min(a.size(), b.size());
for (int i = 0; i < minSize; i++)
{
result.add(a.get(i) + b.get(i));
}
return result;
}
Pattern: Use Math.min() to avoid index errors when sizes differ.
Comparing Two Lists
public static boolean listsEqual(ArrayList<Integer> a,
ArrayList<Integer> b)
{
if (a.size() != b.size())
{
return false;
}
for (int i = 0; i < a.size(); i++)
{
if (!a.get(i).equals(b.get(i)))
{
return false;
}
}
return true;
}
Merging Sorted Lists
public static ArrayList<Integer> merge(ArrayList<Integer> a,
ArrayList<Integer> b)
{
ArrayList<Integer> result = new ArrayList<Integer>();
int i = 0, j = 0;
while (i < a.size() && j < b.size())
{
if (a.get(i) <= b.get(j))
{
result.add(a.get(i));
i++;
}
else
{
result.add(b.get(j));
j++;
}
}
// Add remaining elements
while (i < a.size())
{
result.add(a.get(i));
i++;
}
while (j < b.size())
{
result.add(b.get(j));
j++;
}
return result;
}
Complete Example: Filter and Transform
// Keep only even numbers and double them
public static ArrayList<Integer> processEvens(ArrayList<Integer> nums)
{
ArrayList<Integer> result = new ArrayList<Integer>();
for (int num : nums)
{
if (num % 2 == 0)
{
result.add(num * 2);
}
}
return result;
}
// [1, 2, 3, 4, 5, 6] becomes [4, 8, 12]
Common Mistakes
Mistake 1: Off-by-one for consecutive pairs
// WRONG - accesses size()
for (int i = 0; i < list.size(); i++) {
if (list.get(i) > list.get(i + 1)) { }
}
// WRONG - accesses size()
for (int i = 0; i < list.size(); i++)
{
if (list.get(i) > list.get(i + 1))
{ }
}
Mistake 2: Removing during enhanced for loop
// WRONG - ConcurrentModificationException
for (Integer num : list)
{
if (num < 0)
{
list.remove(num);
}
}
Mistake 3: Not adjusting index after insertion
// WRONG - infinite loop possible
for (int i = 0; i < list.size(); i++)
{
list.add(i, 0); // Missing i++ to skip inserted element
}