Implementing ArrayList Algorithms: Revision Notes (Computer Science A 4.10)

Full explanation and traced examples: Topic 4.10 study guide.

Recap

A standard ArrayList algorithm is a traversal plus a small piece of state. Pick the right starting value and loop bound, update inside the loop, and use the state after it.

int max = list.get(0);                          // maximum
for (int i = 1; i < list.size(); i++)
{
    if (list.get(i) > max) { max = list.get(i); }
}
double avg = (double) sum / list.size();        // average
for (int i = 0; i < list.size() - 1; i++)       // consecutive pairs
{
    // compare list.get(i) and list.get(i + 1)
}

Key relationships

Pattern	Key detail
Maximum / minimum	start from get(0), loop from 1; list must not be empty
Sum / average	cast before dividing; guard size() == 0
Count	start at 0, count++ when the test passes
At least one	return true inside, return false after
All	return false inside, return true after
Consecutive pairs	i < size() - 1
Duplicates	inner loop j = i + 1
Reverse in place	swap i and size() - 1 - i for i < size() / 2
Rotate left / right	add(remove(0)) / add(0, remove(size() - 1))
Insert in order	find index with while (i < size() && get(i) < value), then add(i, value)
Delete matches	loop backwards or hold the index after remove

Assumptions

• The list is not null; for max and min it is not empty.
• For insert in order the list is already sorted ascending.
• Element values are compared with equals (or unboxed) rather than ==.

A mini-example to rehearse

On [4, 9, 2, 9, 7]: maximum 9, sum 31, mean 6.2 (the cast version; without the cast the quotient is 6 as an int). On [1, 3, 2, 5, 6] there are 3 increasing consecutive pairs. Reverse [1, 2, 3, 4] with i < size() / 2 to get [4, 3, 2, 1]; with i < size() you get [1, 2, 3, 4] again. Rotate left gives [2, 3, 4, 1]; insert 6 into [2, 5, 8, 11] gives [2, 5, 6, 8, 11].

Mistakes to avoid

1. A maximum that starts at 0 on negative data.
2. Integer division in an average, and no guard for an empty list.
3. i < list.size() when the loop body uses get(i + 1).
4. Comparing an element with itself in the duplicate search.
5. Visiting the whole list when reversing.
6. Putting get(i) < value before i < size() in a while condition.
7. Returning in an else branch inside an any or all test.

How this topic is usually tested

• Trace an algorithm on a given list and give the returned value or final list.
• Find the line that makes an algorithm wrong, such as a bad start value or loop bound.
• Write a method that finds, counts, tests, inserts or removes.
• Compare two similar methods and say which one is correct.

Quick self-check

1. Maximum of [-5, -2, -9] using max = 0 as the start? 0 (wrong); the correct answer is -2.
2. Mean of [4, 9, 2, 9, 7] with (double) sum / size? 6.2
3. Reverse [1, 2, 3, 4, 5] with i < size() / 2: which indices swap? 0 with 4, and 1 with 3.
4. Rotate [1, 2, 3, 4] left: result? [2, 3, 4, 1]
5. Insert 6 into the sorted [2, 5, 8, 11]: at which index? 2, giving [2, 5, 6, 8, 11].