TOPIC 4.10 · STUDY
Implementing ArrayList Algorithms
ArrayList algorithms walk indexes with get(i) and size(). A minimum starts at the first element and updates when a smaller value appears. A total starts at 0; an int average divides that total by size() with integer division unless a cast to double happens first.
4.10.A
Implementing ArrayList algorithms
An ArrayList algorithm visits each element, usually with a for loop on indexes. Use get(i) to read the value at index i and size() to stop before the end. Stay with a one-dimensional ArrayList. Do not build 2D arrays or sort the list in this topic.
A minimum needs a starting guess that is already in the list. Copy the first element with get(0), then compare every later index. When scores.get(i) is smaller than the stored min, replace min. Starting min at 0 fails when every value is positive, because 0 never appears and never gets replaced.
ArrayList<Integer> scores = new ArrayList<Integer>();
scores.add(8);
scores.add(3);
scores.add(11);
scores.add(3);
int min = scores.get(0);
for (int i = 1; i < scores.size(); i++) {
if (scores.get(i) < min) {
min = scores.get(i);
}
}
System.out.print(min);
Trace the loop. min starts at 8. Index 1 holds 3, which is smaller, so min becomes 3. Index 2 holds 11, which is not smaller. Index 3 holds 3 again, which equals min and does not change it. The print shows 3.
min starts at scores.get(0). Index 1 replaces it with 3; later values do not go lower.
A total uses a different start. Set sum to 0, then add every get(i) from index 0 through size() - 1. After the loop, an average is often sum / scores.size(). When both operands are int, Java uses integer division and drops any fraction. Cast one side to double first if you need a decimal result.
ArrayList<Integer> scores = new ArrayList<Integer>();
scores.add(5);
scores.add(9);
scores.add(4);
int sum = 0;
for (int i = 0; i < scores.size(); i++) {
sum += scores.get(i);
}
System.out.print(sum / scores.size());
The sum is 18 and size() is 3, so 18 / 3 prints 6. Change the list to 5, 9, and 5 and the sum is 19; 19 / 3 prints 6, not 6.333, because both values are int. Writing (double) sum / scores.size() keeps the fraction.
Key points
- Walk an ArrayList with get(i) and stop with size(); stay one-dimensional.
- A minimum starts at get(0), then updates when a later value is smaller.
- A sum starts at 0 and adds every element with +=.
- An int average is sum / size(); integer division drops the fraction.
- Cast to double before dividing if you need a decimal average.
- Do not sort the list for these patterns.
Dividing two ints drops the fraction; cast to double first if you need decimals.