LockInCS

Unit 4 · 20 min

4.10 Implementing ArrayList Algorithms

Every standard ArrayList algorithm is a traversal plus one variable that remembers what you have seen.

Summary, objectives and course and exam description (CED) codes

Standard ArrayList algorithms are traversals with a job: find a minimum or maximum, total the values, test a property, compare neighbors, move elements or insert and delete them. Some algorithms traverse two String, array or ArrayList objects at the same time. On the AP® exam you write these algorithms and trace what they produce.

By the end of this session you can

  • 4.10.A Develop code for standard and original algorithms that involve ArrayList objects, and determine the result of these algorithms.

4.10.A4.10.A.14.10.A.2

Reviewed against the CED on

Know this already? Jump to the checkpoint.

1LearnThe notes, the traps and how to remember them

1. Minimum, maximum, sum and average

An ArrayList algorithm is a traversal with a purpose. For a minimum or maximum, keep the best value seen so far and compare every element with it 4.10.A.1. For a sum, add each element to a running total; for an average, divide that total by size() using double division 4.10.A.1.

ArrayList<Integer> temps = new ArrayList<Integer>();
temps.add(-4);
temps.add(-9);
temps.add(-1);
temps.add(-6);

int max = temps.get(0);
int min = temps.get(0);
int sum = 0;
for (int t : temps)
{
    if (t > max)
    {
        max = t;
    }
    if (t < min)
    {
        min = t;
    }
    sum += t;
}
double avg = (double) sum / temps.size();
System.out.println("max " + max + ", min " + min);
System.out.println("average " + avg);

Output:

max -1, min -9
average -5.0

Watch out: if max started at 0, it would stay 0 for this all-negative list. Seed with the first element. Also, sum / temps.size() with two int values drops the decimal part.

2. Property checks: at least one, all, and how many

Three algorithms ask a yes/no question about each element 4.10.A.1:

Question Variable When to stop early
Does at least one element have the property? boolean Return true at the first match
Do all elements have the property? boolean Return false at the first failure
How many elements have the property? int counter Never: visit every element 
public static boolean anyOver(ArrayList<Integer> scores, int limit)
{
    for (int s : scores)
    {
        if (s > limit)
        {
            return true;
        }
    }
    return false;
}

public static boolean allPassing(ArrayList<Integer> scores)
{
    for (int s : scores)
    {
        if (s < 60)
        {
            return false;
        }
    }
    return true;
}

public static int countEven(ArrayList<Integer> scores)
{
    int count = 0;
    for (int s : scores)
    {
        if (s % 2 == 0)
        {
            count++;
        }
    }
    return count;
}

ArrayList<Integer> scores = new ArrayList<Integer>();
scores.add(72);
scores.add(95);
scores.add(58);
scores.add(80);
System.out.println(anyOver(scores, 90));
System.out.println(allPassing(scores));
System.out.println(countEven(scores));

Output:

true
false
3

Watch out: putting else return true; inside the loop of allPassing makes the method decide after looking at only one element.

3. Consecutive pairs and duplicates

To compare each element with its neighbor, visit all consecutive pairs: get(i) and get(i + 1). The loop must stop at size() - 1 so that i + 1 is still a valid index 4.10.A.1.

To find duplicates, compare every element with every element after it, using nested loops 4.10.A.1. Use equals for objects such as String.

ArrayList<String> playlist = new ArrayList<String>();
playlist.add("Rain");
playlist.add("Echo");
playlist.add("Rain");
playlist.add("Glow");

int changes = 0;
for (int i = 0; i < playlist.size() - 1; i++)
{
    if (playlist.get(i).compareTo(playlist.get(i + 1)) > 0)
    {
        changes++;
    }
}
System.out.println("Out-of-order pairs: " + changes);

boolean hasDuplicate = false;
for (int i = 0; i < playlist.size(); i++)
{
    for (int j = i + 1; j < playlist.size(); j++)
    {
        if (playlist.get(i).equals(playlist.get(j)))
        {
            hasDuplicate = true;
        }
    }
}
System.out.println("Duplicate: " + hasDuplicate);

Output:

Out-of-order pairs: 2
Duplicate: true

The pairs checked are (“Rain”, “Echo”), (“Echo”, “Rain”) and (“Rain”, “Glow”). The first and the last pair are out of alphabetical order. Watch out: with i < playlist.size() the last pass calls get(4) and the program stops with an IndexOutOfBoundsException.

4. Shift, rotate and reverse

A shift moves every element one place left or right. A rotate is a shift where the element that falls off one end comes back at the other end 4.10.A.1. With an ArrayList you can rotate by moving one element: remove(0) returns the first element, and add puts it at the end. You can also do it the array way, with set and a saved value.

To reverse, swap the first and last elements, then the second and second to last, and stop at the middle 4.10.A.1.

ArrayList<Integer> lane = new ArrayList<Integer>();
for (int k = 1; k <= 5; k++)
{
    lane.add(k * 10);
}

// rotate left by one, using set and a saved value
int first = lane.get(0);
for (int i = 0; i < lane.size() - 1; i++)
{
    lane.set(i, lane.get(i + 1));
}
lane.set(lane.size() - 1, first);
System.out.println(lane);

// rotate right by one, using remove and add
lane.add(0, lane.remove(lane.size() - 1));
System.out.println(lane);

// reverse: swap pairs from the outside in
for (int i = 0; i < lane.size() / 2; i++)
{
    int j = lane.size() - 1 - i;
    int temp = lane.get(i);
    lane.set(i, lane.get(j));
    lane.set(j, temp);
}
System.out.println(lane);

Output:

[20, 30, 40, 50, 10]
[10, 20, 30, 40, 50]
[50, 40, 30, 20, 10]

Watch out: if the reverse loop ran to i < lane.size(), it would swap every pair twice and the list would end up back in its original order.

5. Inserting and deleting elements

add(index, obj) inserts and moves later elements right; remove(index) deletes and moves later elements left 4.10.A.1. Both change size(), so a loop that inserts or deletes must control its index carefully.

Deleting. The safest pattern runs backward. The elements that shift are the ones already visited, so nothing is skipped.

ArrayList<Integer> stock = new ArrayList<Integer>();
stock.add(0);
stock.add(0);
stock.add(7);
stock.add(0);
stock.add(3);

// buggy: forward loop always does i++
ArrayList<Integer> copy = new ArrayList<Integer>(stock);
for (int i = 0; i < copy.size(); i++)
{
    if (copy.get(i) == 0)
    {
        copy.remove(i);
    }
}
System.out.println("forward: " + copy);

// correct: backward loop
for (int i = stock.size() - 1; i >= 0; i--)
{
    if (stock.get(i) == 0)
    {
        stock.remove(i);
    }
}
System.out.println("backward: " + stock);

Output:

forward: [0, 7, 3]
backward: [7, 3]

Trace of the buggy loop: at i = 0 the first 0 is removed and the second 0 slides into index 0, but i becomes 1, so that 0 is never checked.

Inserting. After inserting at index i, the element you were looking at is now at i + 1. Skip past the new element so the loop does not process it again (or insert forever).

ArrayList<String> line = new ArrayList<String>();
line.add("Ana");
line.add("VIP");
line.add("Ben");
line.add("VIP");

for (int i = 0; i < line.size(); i++)
{
    if (line.get(i).equals("VIP"))
    {
        line.add(i, "Guard");
        i++; // jump over the element we just inserted
    }
}
System.out.println(line);

Output:

[Ana, Guard, VIP, Ben, Guard, VIP]

Watch out: calling add or remove on a list inside an enhanced for loop over that same list throws a ConcurrentModificationException.

6. Traversing more than one collection at a time

Some algorithms need two String, array or ArrayList objects at once 4.10.A.2. Two common shapes:

  • Parallel traversal: one index walks through both collections, so element i of one belongs with element i of the other.
  • Nested traversal: for each element of the first collection, walk through the whole second collection.
String[] players = {"Kai", "Lena", "Omar"};
ArrayList<Integer> goals = new ArrayList<Integer>();
goals.add(3);
goals.add(5);
goals.add(2);

String best = players[0];
int bestGoals = goals.get(0);
for (int i = 1; i < players.length; i++)
{
    if (goals.get(i) > bestGoals)
    {
        bestGoals = goals.get(i);
        best = players[i];
    }
}
System.out.println(best + " scored " + bestGoals);

// count letters of a word that also appear in a second word
String a = "plane";
String b = "apple";
int shared = 0;
for (int i = 0; i < a.length(); i++)
{
    if (b.indexOf(a.substring(i, i + 1)) >= 0)
    {
        shared++;
    }
}
System.out.println("shared letters: " + shared);

Output:

Lena scored 5
shared letters: 4

In “plane”, the letters p, l, a and e appear in “apple”; n does not. Watch out: parallel traversal only works if both collections have the same length, or if the loop stops at the shorter one.

Lock it in: memory hooks

  • Min and maxSeed with a real element, then challenge it: the champion keeps the title until someone beats it.
  • Deleting in a loopRemove going backward: the elements that shift are the ones you already visited.
  • Consecutive pairsPairs need two people: stop one step early, so i + 1 is always a real index.

Common misconceptions

  • "You can remove elements in a forward for loop and simply move on with i++."

    Not quite. After remove(i), every later element shifts one index left, so i++ skips the element that moved into position i. Loop backward, or only increase i when nothing was removed.

  • "Starting the maximum at 0 always works."

    Not quite. If every value is negative, 0 is never replaced and the answer is wrong. Start with the first element (or Integer.MIN_VALUE).

  • "An "all elements" check can return true as soon as one element passes."

    Not quite. One passing element proves nothing about the others. Return false at the first failure and return true only after the loop ends.

  • "size() and length work the same way on an ArrayList."

    Not quite. An ArrayList uses the method call list.size() with parentheses. Arrays use the length attribute and strings use length().

Exam traps

  • Forward loop with remove(i) and i++ skips the element right after each removal.
  • Pair loops that run to i < list.size() and read list.get(i + 1) throw an IndexOutOfBoundsException on the last pass.
  • sum / list.size() with an int sum is integer division; cast to double first.
  • An enhanced for loop that calls add or remove on the same list throws a ConcurrentModificationException.
  • Rotating left: save the first element before the shift loop overwrites it.

2PracticeRecall it, then check yourself

In 30 seconds

  1. Most ArrayList algorithms are one traversal plus a variable that remembers something (a best value, a total, a count or a flag).
  2. Seed min and max with the first element, compute averages with double division, and stop pair loops at size() - 1.
  3. "At least one" returns true early; "all" returns false early.
  4. add and remove change the size and shift later elements, so loops that insert or delete must adjust the index.
  5. Some algorithms traverse two collections together with one shared index, or with nested loops.

Cover this list, say the points out loud, then take the checkpoint without scrolling back up.

Checkpoint · 5 questions

Checkpoint: Implementing ArrayList Algorithms

Pick an answer to mark it. Every answer is explained, and you can try any question again. Your saved score counts first tries only, and stays in this browser.

  1. 1 Consider the following code segment, which is intended to remove every even number from nums. What is printed as a result of executing the code segment? 4.10.A.1 
    ArrayList<Integer> nums = new ArrayList<Integer>();
nums.add(4);
nums.add(4);
nums.add(5);
nums.add(4);
nums.add(6);
for (int i = 0; i < nums.size(); i++)
{
    if (nums.get(i) % 2 == 0)
    {
        nums.remove(i);
    }
}
System.out.println(nums);
    Show answer

    Answer: B. When remove(i) deletes an element, the next element slides into index i, but i++ moves past it. At i = 0 the first 4 is removed and the second 4 moves to index 0 unchecked; at i = 2 the third 4 is removed and 6 moves to index 2 unchecked. The result is [4, 5, 6]. [5] is what a correct backward loop would print, and [5, 6] and [4, 5] each assume only one element was skipped.

  2. 2 The following method is intended to return true if every element of nums is positive and false otherwise. For which of the following lists does the method NOT return the intended value? 4.10.A.1 
    public static boolean allPositive(ArrayList<Integer> nums)
{
    for (int n : nums)
    {
        if (n <= 0)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
    return true;
}
    Show answer

    Answer: C. The else branch returns true after checking only the first element, so the method decides based on nums.get(0) alone. For [6, -1, 4] the first element is positive, so it returns true even though -1 is not positive. For [3, 7, 9] true is correct, and for [-2, 5, 8] and [0, 0, 0] the first element fails, so false is correct.

  3. 3 Consider the following code segment. What is printed as a result of executing the code segment? 4.10.A.1 
    ArrayList<String> letters = new ArrayList<String>();
letters.add("a");
letters.add("b");
letters.add("c");
letters.add("d");
for (int k = 0; k < 2; k++)
{
    String last = letters.remove(letters.size() - 1);
    letters.add(0, last);
}
System.out.println(letters);
    Show answer

    Answer: A. Each pass removes the last element and inserts it at index 0, which rotates the list right by one. After the first pass the list is [d, a, b, c]; after the second it is [c, d, a, b]. [d, a, b, c] stops after one pass, [b, c, d, a] is a rotation to the left, and [a, b, c, d] would need four passes.

  4. 4 Consider the following code segment. What is printed as a result of executing the code segment? 4.10.A.1 
    ArrayList<Integer> rolls = new ArrayList<Integer>();
rolls.add(2);
rolls.add(2);
rolls.add(3);
rolls.add(3);
rolls.add(3);
rolls.add(1);
int same = 0;
for (int i = 0; i < rolls.size() - 1; i++)
{
    int a = rolls.get(i);
    int b = rolls.get(i + 1);
    if (a == b)
    {
        same++;
    }
}
System.out.println(same);
    Show answer

    Answer: D. The loop visits the consecutive pairs (2, 2), (2, 3), (3, 3), (3, 3) and (3, 1). Three of them hold equal values. 2 counts runs of equal values instead of pairs, 5 counts every pair, and 4 would need one more equal pair.

  5. 5 A word game compares a secret String with a player's guess, stored one letter per element in an ArrayList. Consider the following code segment. What is printed as a result of executing the code segment? 4.10.A.2 
    String secret = "CRANE";
ArrayList<String> guess = new ArrayList<String>();
guess.add("C");
guess.add("A");
guess.add("R");
guess.add("N");
guess.add("E");
int exact = 0;
for (int i = 0; i < secret.length(); i++)
{
    if (secret.substring(i, i + 1).equals(guess.get(i)))
    {
        exact++;
    }
}
System.out.println(exact);
    Show answer

    Answer: B. The single index i traverses the String and the ArrayList at the same time. Positions 0 (C), 3 (N) and 4 (E) match; positions 1 and 2 hold the same letters in a different order, so they do not count. 5 counts letters that appear anywhere, and 2 and 4 miscount the matching positions.

3PrevailLock it in for exam day

By the numbers

Name each list from memory, then reveal it to check. Each list shows how many items to recall.

  • Standard ArrayList algorithms that use traversals eleven algorithms CED 4.10.A.1
    1. minimum or maximum
    2. sum or average
    3. at least one element has a property
    4. all elements have a property
    5. number of elements with a property
    6. all consecutive pairs
    7. presence or absence of duplicates
    8. shift or rotate left or right
    9. reverse the order
    10. insert elements
    11. delete elements
  • Object types an algorithm may traverse simultaneously three types CED 4.10.A.2
    1. String
    2. array
    3. ArrayList

Key terms: flip the cards

Read the term, say the definition out loud, then flip to check. Struggling a little to remember is what makes it stick.

  • ArrayListtap to flip

    A java.util class for a list of object references that can grow and shrink; ArrayList<E> names the element type E.

    Example and CED codes
  • Traversaltap to flip

    Using repetition (or recursion) to access all elements of an array or ArrayList, or an ordered sequence of them.

    Example and CED codes
  • Arraytap to flip

    An object that stores a fixed number of values of the same type, either primitive values or object references, reached by an index.

    Example and CED codes
  • Indextap to flip

    The position of a character in a String, counted from 0. Valid indices run from 0 to length() - 1.

    Example and CED codes
  • for looptap to flip

    An iterative statement whose header has three parts: the initialization (runs once), the Boolean expression (checked before each iteration) and the update (after each iteration).

    Example and CED codes
  • Linear searchtap to flip

    A search algorithm that checks each element in order until it finds the desired value or has checked every element.

    Example and CED codes

Questions students ask

How do you remove elements from an ArrayList inside a loop in Java?

Use an indexed for loop that runs backward from size() - 1 down to 0, or a forward loop that only increases the index when no element was removed. Never call remove inside an enhanced for loop over the same list.

How do you find the maximum value in an ArrayList of Integer?

Store list.get(0) in a variable, traverse the rest of the list, and replace the variable whenever an element is greater. Unboxing turns each Integer into an int for the comparison.

How do you check an ArrayList for duplicates?

Use nested loops: the outer loop picks an element and the inner loop compares it with every element after it. If any pair is equal, there is a duplicate.

Which ArrayList algorithms are on the AP® Computer Science A exam?

Minimum and maximum, sum and average, property checks (at least one, all, count), consecutive pairs, duplicates, shifting or rotating, reversing, inserting and deleting elements, plus algorithms that traverse more than one collection at once.

Was this page helpful?

No names are ever shown, and every public comment is checked by us first. Please do not include personal details. To get a reply, email [email protected].

↑ Top

Enlarged view of the selected figure