Implementing ArrayList Algorithms

A fitness app records your step count once a day. On day 1 there is one number; after a month there are thirty. An array would need its length fixed in advance, so the app keeps the counts in an ArrayList<Integer> that grows by one each day. At the end of the week it wants the total, the daily average, and the best and worst days.

You already know these algorithms. In Topic 4.5 you added up an array with an accumulator, divided by the length for an average, and tracked the largest value seen so far. Every one of those algorithms works on an ArrayList too. Only the way you reach the elements changes:

Note that length has no parentheses but size() does, because size() is a method call. Every algorithm in this chapter is built on a traversal (Topic 4.9): a loop that visits the elements of a list in order. A standard algorithm is a common pattern, such as a sum or a maximum, that you can reuse in many programs by changing the list and the condition.

import java.util.ArrayList;

public class SumAverage
{
    public static void main(String[] args)
    {
        ArrayList<Integer> steps = new ArrayList<Integer>();
        steps.add(4200);
        steps.add(6100);
        steps.add(3800);
        steps.add(7500);
        steps.add(5400);

        int total = 0;
        for (int i = 0; i < steps.size(); i++)
        {
            total += steps.get(i);
        }
        double average = (double) total / steps.size();
        System.out.println("Total: " + total);
        System.out.println("Average: " + average);
    }
}

Total: 27000
Average: 5400.0

An average divides by size(), so it needs a list with at least one element. This is a precondition of the algorithm: something that must be true before it runs.

For a minimum or maximum, start with a value that really is in the list, the first element, and compare every other element against it.

import java.util.ArrayList;

public class MinMaxTemps
{
    public static void main(String[] args)
    {
        ArrayList<Integer> temps = new ArrayList<Integer>();
        temps.add(-3);
        temps.add(5);
        temps.add(-8);
        temps.add(2);
        temps.add(0);

        int lowest = temps.get(0);
        int highest = temps.get(0);
        for (int i = 1; i < temps.size(); i++)
        {
            int temp = temps.get(i);
            if (temp < lowest)
            {
                lowest = temp;
            }
            if (temp > highest)
            {
                highest = temp;
            }
        }
        System.out.println("Lowest: " + lowest);
        System.out.println("Highest: " + highest);
    }
}

Lowest: -8
Highest: 5

import java.util.ArrayList;

public class MaxStartZero
{
    public static void main(String[] args)
    {
        ArrayList<Integer> temps = new ArrayList<Integer>();
        temps.add(-4);
        temps.add(-9);
        temps.add(-2);

        int highest = 0;
        for (int temp : temps)
        {
            if (temp > highest)
            {
                highest = temp;
            }
        }
        System.out.println("Highest: " + highest);
    }
}

Highest: 0

import java.util.ArrayList;

public class LongestWord
{
    public static void main(String[] args)
    {
        ArrayList<String> words = new ArrayList<String>();
        words.add("fig");
        words.add("banana");
        words.add("kiwi");
        words.add("cherry");
        words.add("plum");

        String longest = words.get(0);
        for (int i = 1; i < words.size(); i++)
        {
            if (words.get(i).length() > longest.length())
            {
                longest = words.get(i);
            }
        }
        System.out.println(longest);
    }
}

banana

A teacher’s grade list raises three different questions. Did anyone score below 70? Did everyone pass? How many students earned an A? Each is a yes-or-no question or a count about the elements of the list, and each needs a full traversal.

The tools are the ones from Topic 4.5:

• At least one: a boolean flag starts false and switches to true the first time an element has the property.
• All: a flag starts true and switches to false the first time an element does not have the property. One counterexample is enough to make “all” false.
• How many: an int counter starts at 0 and goes up by 1 for each element with the property.

None of these changes the list, so an enhanced for loop (Topic 4.9) is a good fit: it hands you each element in turn without an index. When the list holds Integer objects, the loop variable can be declared int, and Java unboxes each element as it is assigned.

import java.util.ArrayList;

public class GradeChecks
{
    public static void main(String[] args)
    {
        ArrayList<Integer> grades = new ArrayList<Integer>();
        grades.add(88);
        grades.add(92);
        grades.add(67);
        grades.add(95);
        grades.add(74);

        boolean anyBelow70 = false;
        boolean allPassing = true;
        int countA = 0;
        for (int grade : grades)
        {
            if (grade < 70)
            {
                anyBelow70 = true;
            }
            if (grade < 60)
            {
                allPassing = false;
            }
            if (grade >= 90)
            {
                countA++;
            }
        }
        System.out.println("Any below 70: " + anyBelow70);
        System.out.println("All passing: " + allPassing);
        System.out.println("A grades: " + countA);
    }
}

Any below 70: true
All passing: true
A grades: 2

The same patterns work on a list of strings. Here the “all” flag and the counter share one if/else: an element either has the property (count it) or it does not (it breaks “all”).

import java.util.ArrayList;

public class TagChecks
{
    public static void main(String[] args)
    {
        ArrayList<String> tags = new ArrayList<String>();
        tags.add("#java");
        tags.add("#code");
        tags.add("fun");
        tags.add("#ap");

        boolean allTags = true;
        int tagCount = 0;
        for (String tag : tags)
        {
            if (tag.substring(0, 1).equals("#"))
            {
                tagCount++;
            }
            else
            {
                allTags = false;
            }
        }
        System.out.println("All hashtags: " + allTags);
        System.out.println("Hashtags: " + tagCount);
    }
}

All hashtags: false
Hashtags: 3

import java.util.ArrayList;

public class FlagElseBug
{
    public static void main(String[] args)
    {
        ArrayList<Integer> grades = new ArrayList<Integer>();
        grades.add(55);
        grades.add(80);
        grades.add(90);

        boolean allPassing = true;
        for (int grade : grades)
        {
            if (grade < 60)
            {
                allPassing = false;
            }
            else
            {
                allPassing = true;
            }
        }
        System.out.println("All passing: " + allPassing);
    }
}

All passing: true

import java.util.ArrayList;

public class CountRange
{
    public static void main(String[] args)
    {
        ArrayList<Integer> values = new ArrayList<Integer>();
        values.add(12);
        values.add(55);
        values.add(20);
        values.add(9);
        values.add(31);
        values.add(10);

        int inRange = 0;
        boolean over50 = false;
        for (int value : values)
        {
            if (value >= 10 && value <= 20)
            {
                inRange++;
            }
            if (value > 50)
            {
                over50 = true;
            }
        }
        System.out.println(inRange + " " + over50);
    }
}

3 true

boolean result = true;
for (String name : names)
{
    if (name.length() < 3)
    {
        result = false;
    }
}

A stock-price app keeps one closing price per day. To report “the price rose 3 times this week,” it has to compare each day with the next day. A school database storing student ID numbers has a different worry: does any ID appear twice? Both questions look at two elements at a time instead of one.

Consecutive pairs

Consecutive elements are elements next to each other, at indices i and i + 1. To visit every consecutive pair, the loop must stop one index early. In a list of 5 elements, the pairs start at indices 0, 1, 2, and 3; a pair starting at index 4 would need index 5, which does not exist. So the condition is i < list.size() - 1.

import java.util.ArrayList;

public class ConsecutiveRises
{
    public static void main(String[] args)
    {
        ArrayList<Integer> prices = new ArrayList<Integer>();
        prices.add(20);
        prices.add(22);
        prices.add(21);
        prices.add(25);
        prices.add(30);

        int rises = 0;
        int biggestJump = 0;
        for (int i = 0; i < prices.size() - 1; i++)
        {
            int today = prices.get(i);
            int tomorrow = prices.get(i + 1);
            if (tomorrow > today)
            {
                rises++;
                if (tomorrow - today > biggestJump)
                {
                    biggestJump = tomorrow - today;
                }
            }
        }
        System.out.println("Rises: " + rises);
        System.out.println("Biggest jump: " + biggestJump);
    }
}

Rises: 3
Biggest jump: 5

import java.util.ArrayList;

public class PairsTooFar
{
    public static void main(String[] args)
    {
        ArrayList<Integer> prices = new ArrayList<Integer>();
        prices.add(20);
        prices.add(22);
        prices.add(21);
        prices.add(25);
        prices.add(30);

        for (int i = 0; i < prices.size(); i++)
        {
            System.out.println(prices.get(i) + " -> " + prices.get(i + 1));
        }
    }
}

20 -> 22
22 -> 21
21 -> 25
25 -> 30
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 5 out of bounds for length 5

Duplicates

To find out whether any value appears twice, every element must be compared with every other element, not only its neighbor, since the two copies could be far apart. That calls for nested loops (Topic 2.11): the outer loop picks an element at index i, and the inner loop compares it with every element after it, starting at j = i + 1. Starting after i means an element is never compared with itself, and each pair is checked only once.

import java.util.ArrayList;

public class HasDuplicate
{
    public static void main(String[] args)
    {
        ArrayList<Integer> ids = new ArrayList<Integer>();
        ids.add(104);
        ids.add(317);
        ids.add(250);
        ids.add(317);
        ids.add(999);

        boolean duplicate = false;
        for (int i = 0; i < ids.size(); i++)
        {
            for (int j = i + 1; j < ids.size(); j++)
            {
                int first = ids.get(i);
                int second = ids.get(j);
                if (first == second)
                {
                    duplicate = true;
                    System.out.println("Match at " + i + " and " + j);
                }
            }
        }
        System.out.println("Has duplicate: " + duplicate);
    }
}

Match at 1 and 3
Has duplicate: true

import java.util.ArrayList;

public class IntegerEqualsBug
{
    public static void main(String[] args)
    {
        ArrayList<Integer> ids = new ArrayList<Integer>();
        ids.add(1000);
        ids.add(2000);
        ids.add(1000);

        boolean duplicate = false;
        for (int i = 0; i < ids.size(); i++)
        {
            for (int j = i + 1; j < ids.size(); j++)
            {
                if (ids.get(i) == ids.get(j))
                {
                    duplicate = true;
                }
            }
        }
        System.out.println("Has duplicate: " + duplicate);
    }
}

Has duplicate: false

import java.util.ArrayList;

public class DupSelfBug
{
    public static void main(String[] args)
    {
        ArrayList<Integer> codes = new ArrayList<Integer>();
        codes.add(4);
        codes.add(8);
        codes.add(15);

        boolean duplicate = false;
        for (int i = 0; i < codes.size(); i++)
        {
            for (int j = 0; j < codes.size(); j++)
            {
                int first = codes.get(i);
                int second = codes.get(j);
                if (first == second)
                {
                    duplicate = true;
                }
            }
        }
        System.out.println("Has duplicate: " + duplicate);
    }
}

for (int j = i + 1; j < codes.size(); j++)

import java.util.ArrayList;

public class AdjacentRepeats
{
    public static void main(String[] args)
    {
        ArrayList<String> words = new ArrayList<String>();
        words.add("the");
        words.add("the");
        words.add("cat");
        words.add("sat");
        words.add("sat");
        words.add("sat");

        int repeats = 0;
        for (int i = 1; i < words.size(); i++)
        {
            if (words.get(i).equals(words.get(i - 1)))
            {
                repeats++;
            }
        }
        System.out.println(repeats);
    }
}

3

A race app keeps finish times in order, fastest first. When a new runner finishes, the time has to go into the right place, not at the end. With an array this was hard, because an array’s length cannot change. An ArrayList can grow, and its add(index, value) method from Topic 4.8 makes room by moving the element at index, and every element after it, one place to the right.

To insert in order, traverse until you find the first element bigger than the new value, then add the new value at that index.

import java.util.ArrayList;

public class InsertInOrder
{
    public static void insertInOrder(ArrayList<Integer> list, int value)
    {
        int index = 0;
        while (index < list.size() && list.get(index) < value)
        {
            index++;
        }
        list.add(index, value);
    }

    public static void main(String[] args)
    {
        ArrayList<Integer> times = new ArrayList<Integer>();
        times.add(10);
        times.add(25);
        times.add(40);
        times.add(55);

        System.out.println(times);
        insertInOrder(times, 30);
        System.out.println(times);
        insertInOrder(times, 70);
        System.out.println(times);
        insertInOrder(times, 5);
        System.out.println(times);
    }
}

[10, 25, 40, 55]
[10, 25, 30, 40, 55]
[10, 25, 30, 40, 55, 70]
[5, 10, 25, 30, 40, 55, 70]

Inserting during a traversal needs one more step. Say a to-do list should get a study task in front of every test. When the loop finds test at index i and inserts study there, test moves to index i + 1. The loop’s own i++ would land right back on that same test, insert again, and repeat forever. The fix is an extra i++ after inserting, which moves past the new element so the loop’s i++ then moves past the test.

import java.util.ArrayList;

public class InsertStudy
{
    public static void main(String[] args)
    {
        ArrayList<String> tasks = new ArrayList<String>();
        tasks.add("laundry");
        tasks.add("test");
        tasks.add("dishes");
        tasks.add("test");

        for (int i = 0; i < tasks.size(); i++)
        {
            if (tasks.get(i).equals("test"))
            {
                tasks.add(i, "study");
                i++;
            }
        }
        System.out.println(tasks);
    }
}

[laundry, study, test, dishes, study, test]

for (int i = 0; i < tasks.size(); i++)
{
    if (tasks.get(i).equals("test"))
    {
        tasks.add(i, "study");
    }
}

import java.util.ArrayList;

public class InsertAfterEven
{
    public static void main(String[] args)
    {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(3);
        nums.add(4);
        nums.add(7);
        nums.add(8);

        for (int i = 0; i < nums.size(); i++)
        {
            if (nums.get(i) % 2 == 0)
            {
                nums.add(i + 1, 0);
                i++;
            }
        }
        System.out.println(nums);
    }
}

[3, 4, 0, 7, 8, 0]

The teacher from 4.10.2 wants to drop every score below 60 from a list before computing a class average. Removing elements one at a time during a traversal sounds simple, but remove(i) from Topic 4.8 moves every later element one place left. The element that was at i + 1 is now at i, and a loop that goes on to i + 1 never looks at it.

import java.util.ArrayList;

public class RemoveSkipBug
{
    public static void main(String[] args)
    {
        ArrayList<Integer> scores = new ArrayList<Integer>();
        scores.add(55);
        scores.add(48);
        scores.add(90);
        scores.add(30);

        for (int i = 0; i < scores.size(); i++)
        {
            if (scores.get(i) < 60)
            {
                scores.remove(i);
            }
        }
        System.out.println(scores);
    }
}

[48, 90]

There are two standard fixes. The first moves forward but adds 1 to the index only when nothing was removed. A while loop makes that easy to write.

import java.util.ArrayList;

public class RemoveForwardFixed
{
    public static void main(String[] args)
    {
        ArrayList<Integer> scores = new ArrayList<Integer>();
        scores.add(55);
        scores.add(48);
        scores.add(90);
        scores.add(30);

        int i = 0;
        while (i < scores.size())
        {
            if (scores.get(i) < 60)
            {
                scores.remove(i);
            }
            else
            {
                i++;
            }
        }
        System.out.println(scores);
    }
}

The check at i = 1 then finds 1 < 1 false. The program prints [90].

The second fix traverses backward, from the last index down to 0. Removing at i moves only the elements to the right of i, and those have already been checked, so nothing that still needs checking moves.

import java.util.ArrayList;

public class RemoveBackward
{
    public static void main(String[] args)
    {
        ArrayList<Integer> scores = new ArrayList<Integer>();
        scores.add(55);
        scores.add(48);
        scores.add(90);
        scores.add(30);

        for (int i = scores.size() - 1; i >= 0; i--)
        {
            if (scores.get(i) < 60)
            {
                scores.remove(i);
            }
        }
        System.out.println(scores);
    }
}

[90]

import java.util.ArrayList;

public class RemoveEnhancedFor
{
    public static void main(String[] args)
    {
        ArrayList<Integer> scores = new ArrayList<Integer>();
        scores.add(55);
        scores.add(90);
        scores.add(48);

        int index = 0;
        for (int score : scores)
        {
            if (score < 60)
            {
                scores.remove(index);
            }
            index++;
        }
        System.out.println(scores);
    }
}

Exception in thread "main" java.util.ConcurrentModificationException

import java.util.ArrayList;

public class RemoveShortWords
{
    public static void main(String[] args)
    {
        ArrayList<String> words = new ArrayList<String>();
        words.add("a");
        words.add("be");
        words.add("cat");
        words.add("do");
        words.add("eagle");

        for (int i = words.size() - 1; i >= 0; i--)
        {
            if (words.get(i).length() < 3)
            {
                words.remove(i);
            }
        }
        System.out.println(words);
    }
}

[cat, eagle]

// I
for (int i = 0; i < list.size(); i++)
{
    if (list.get(i) % 2 == 0)
    {
        list.remove(i);
    }
}

// II
for (int i = list.size() - 1; i >= 0; i--)
{
    if (list.get(i) % 2 == 0)
    {
        list.remove(i);
    }
}

// III
int k = 0;
while (k < list.size())
{
    if (list.get(k) % 2 == 0)
    {
        list.remove(k);
    }
    else
    {
        k++;
    }
}

A weather display shows the last four temperature readings. When a new reading arrives, the oldest one drops off the front and the new one joins at the back. A board game passes the turn around a table, and after the last player it is the first player’s turn again. In Topic 4.5, moving every element of an array one place took a loop that copied element after element. With an ArrayList, remove and add do the moving for you.

Two terms describe these moves:

• To shift a list is to move every element one place left or right. One element falls off one end, and a new value fills the empty spot at the other end.
• To rotate a list is to shift it with wraparound: the element that falls off one end comes back in at the other end, so no element is lost.

import java.util.ArrayList;

public class ShiftWindow
{
    public static void main(String[] args)
    {
        ArrayList<Integer> window = new ArrayList<Integer>();
        window.add(3);
        window.add(5);
        window.add(4);
        window.add(6);

        System.out.println(window);
        window.remove(0);
        window.add(8);
        System.out.println(window);
        window.remove(window.size() - 1);
        window.add(0, 0);
        System.out.println(window);
    }
}

[3, 5, 4, 6]
[5, 4, 6, 8]
[0, 5, 4, 6]

A rotation uses the fact that remove returns the element it removed (Topic 4.8). Save it, then add it back at the other end.

import java.util.ArrayList;

public class RotateTurns
{
    public static void main(String[] args)
    {
        ArrayList<String> turns = new ArrayList<String>();
        turns.add("Ana");
        turns.add("Ben");
        turns.add("Cy");
        turns.add("Dee");

        System.out.println(turns);
        String first = turns.remove(0);
        turns.add(first);
        System.out.println(turns);
        String last = turns.remove(turns.size() - 1);
        turns.add(0, last);
        System.out.println(turns);
    }
}

[Ana, Ben, Cy, Dee]
[Ben, Cy, Dee, Ana]
[Ana, Ben, Cy, Dee]

To reverse a list in place, swap the first and last elements, then the second and second-to-last, and so on toward the middle. A swap needs a temporary variable, just as with arrays in Topic 4.5, because the first set overwrites one of the two values.

import java.util.ArrayList;

public class ReverseList
{
    public static void main(String[] args)
    {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(1);
        nums.add(2);
        nums.add(3);
        nums.add(4);
        nums.add(5);

        int last = nums.size() - 1;
        for (int i = 0; i < nums.size() / 2; i++)
        {
            int temp = nums.get(i);
            nums.set(i, nums.get(last - i));
            nums.set(last - i, temp);
        }
        System.out.println(nums);
    }
}

[5, 4, 3, 2, 1]

import java.util.ArrayList;

public class ReverseTwice
{
    public static void main(String[] args)
    {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(1);
        nums.add(2);
        nums.add(3);
        nums.add(4);
        nums.add(5);

        int last = nums.size() - 1;
        for (int i = 0; i < nums.size(); i++)
        {
            int temp = nums.get(i);
            nums.set(i, nums.get(last - i));
            nums.set(last - i, temp);
        }
        System.out.println(nums);
    }
}

[1, 2, 3, 4, 5]

import java.util.ArrayList;

public class RotateLoop
{
    public static void main(String[] args)
    {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(1);
        nums.add(2);
        nums.add(3);
        nums.add(4);
        nums.add(5);

        for (int k = 0; k < 2; k++)
        {
            nums.add(0, nums.remove(nums.size() - 1));
        }
        System.out.println(nums);
    }
}

[4, 5, 1, 2, 3]

import java.util.ArrayList;

public class SwapNoTemp
{
    public static void main(String[] args)
    {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(10);
        nums.add(20);
        nums.add(30);
        nums.add(40);
        nums.add(50);
        nums.add(60);

        int last = nums.size() - 1;
        for (int i = 0; i < nums.size() / 2; i++)
        {
            nums.set(i, nums.get(last - i));
            nums.set(last - i, nums.get(i));
        }
        System.out.println(nums);
    }
}

[60, 50, 40, 40, 50, 60]

Deleting from a list changes it for good. Often a program needs the original data later, such as every score for the class average and a separate list of just the failing scores to send home. Instead of removing elements from the original, you can build a second list.

The pattern: create a new, empty ArrayList, traverse the original, and add each element that has the property. The result is a filtered list. The original is only read, never changed, so an enhanced for loop is safe, and no element can be skipped.

import java.util.ArrayList;

public class BeforeM
{
    public static void main(String[] args)
    {
        ArrayList<String> fruits = new ArrayList<String>();
        fruits.add("apple");
        fruits.add("kiwi");
        fruits.add("mango");
        fruits.add("fig");
        fruits.add("peach");

        ArrayList<String> early = new ArrayList<String>();
        for (String fruit : fruits)
        {
            if (fruit.compareTo("m") < 0)
            {
                early.add(fruit);
            }
        }
        System.out.println(early);
        System.out.println(fruits.size() + " " + early.size());
    }
}

[apple, kiwi, fig]
5 3

import java.util.ArrayList;

public class FilterAddBug
{
    public static void main(String[] args)
    {
        ArrayList<Integer> nums = new ArrayList<Integer>();
        nums.add(4);
        nums.add(12);
        nums.add(7);
        nums.add(15);

        ArrayList<Integer> big = new ArrayList<Integer>();
        for (int n : nums)
        {
            if (n > 10)
            {
                nums.add(n);
            }
        }
        System.out.println(big);
    }
}

Exception in thread "main" java.util.ConcurrentModificationException

A class keeps student names in an array and their GPAs in an ArrayList<Double>, with the GPA at index i belonging to the name at index i. To print the honor roll, the program has to read both collections together. Some algorithms need several strings, arrays, or lists traversed at the same time.

When the collections line up by position, one loop index can serve all of them: names[i] and gpas.get(i) refer to the same student. The one rule is that the loop bound must keep i valid in every collection it reads.

import java.util.ArrayList;

public class HonorRoll
{
    public static void main(String[] args)
    {
        String[] names = {"Ava", "Ben", "Cleo", "Dev"};
        ArrayList<Double> gpas = new ArrayList<Double>();
        gpas.add(3.8);
        gpas.add(3.2);
        gpas.add(3.9);
        gpas.add(3.5);

        ArrayList<String> honorRoll = new ArrayList<String>();
        for (int i = 0; i < names.length; i++)
        {
            if (gpas.get(i) >= 3.5)
            {
                honorRoll.add(names[i]);
            }
        }
        System.out.println(honorRoll);
        System.out.println(gpas);
    }
}

[Ava, Cleo, Dev]
[3.8, 3.2, 3.9, 3.5]

A string can be one of the collections, too. Here a quiz’s answer key is a String, one letter per question, and a student’s answers are in an ArrayList<String>.

import java.util.ArrayList;

public class QuizKey
{
    public static void main(String[] args)
    {
        String key = "BDAC";
        ArrayList<String> answers = new ArrayList<String>();
        answers.add("B");
        answers.add("A");
        answers.add("A");
        answers.add("C");

        int correct = 0;
        ArrayList<Integer> missed = new ArrayList<Integer>();
        for (int i = 0; i < answers.size(); i++)
        {
            if (answers.get(i).equals(key.substring(i, i + 1)))
            {
                correct++;
            }
            else
            {
                missed.add(i + 1);
            }
        }
        System.out.println("Correct: " + correct);
        System.out.println("Missed: " + missed);
    }
}

Correct: 3
Missed: [2]

import java.util.ArrayList;

public class ShortAnswersBug
{
    public static void main(String[] args)
    {
        String key = "BDAC";
        ArrayList<String> answers = new ArrayList<String>();
        answers.add("B");
        answers.add("A");
        answers.add("A");

        for (int i = 0; i < key.length(); i++)
        {
            if (answers.get(i).equals(key.substring(i, i + 1)))
            {
                System.out.println("Question " + (i + 1) + ": right");
            }
            else
            {
                System.out.println("Question " + (i + 1) + ": wrong");
            }
        }
    }
}

Question 1: right
Question 2: wrong
Question 3: right
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 3 out of bounds for length 3

import java.util.ArrayList;

public class LargerOfPairs
{
    public static void main(String[] args)
    {
        ArrayList<Integer> a = new ArrayList<Integer>();
        a.add(3);
        a.add(8);
        a.add(2);
        ArrayList<Integer> b = new ArrayList<Integer>();
        b.add(5);
        b.add(1);
        b.add(2);

        ArrayList<Integer> larger = new ArrayList<Integer>();
        for (int i = 0; i < a.size(); i++)
        {
            larger.add(Math.max(a.get(i), b.get(i)));
        }
        System.out.println(larger);
    }
}

A classroom sensor records a reading every minute and stores -1 whenever it fails to read. Before the data can be used, the bad readings must go. Then the program reports the average, the readings above average, and whether any reading repeated two minutes in a row. Each job is a separate method, and each method is one algorithm from this chapter.

import java.util.ArrayList;

public class CleanReadings
{
    public static void removeInvalid(ArrayList<Integer> list)
    {
        for (int i = list.size() - 1; i >= 0; i--)
        {
            if (list.get(i) < 0)
            {
                list.remove(i);
            }
        }
    }

    public static double average(ArrayList<Integer> list)
    {
        int total = 0;
        for (int value : list)
        {
            total += value;
        }
        return (double) total / list.size();
    }

    public static ArrayList<Integer> aboveAverage(ArrayList<Integer> list, double avg)
    {
        ArrayList<Integer> result = new ArrayList<Integer>();
        for (int value : list)
        {
            if (value > avg)
            {
                result.add(value);
            }
        }
        return result;
    }

    public static boolean hasRepeatInARow(ArrayList<Integer> list)
    {
        for (int i = 0; i < list.size() - 1; i++)
        {
            int current = list.get(i);
            int next = list.get(i + 1);
            if (current == next)
            {
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args)
    {
        ArrayList<Integer> readings = new ArrayList<Integer>();
        readings.add(12);
        readings.add(-1);
        readings.add(15);
        readings.add(15);
        readings.add(-1);
        readings.add(20);
        readings.add(9);

        removeInvalid(readings);
        System.out.println("Cleaned: " + readings);
        double avg = average(readings);
        System.out.println("Average: " + avg);
        System.out.println("Above average: " + aboveAverage(readings, avg));
        System.out.println("Repeat in a row: " + hasRepeatInARow(readings));
    }
}

Step 1, removeInvalid (lines 5–14), deletes while traversing (4.10.5). It walks backward and removes every negative reading. The list readings in main is changed, because the parameter list refers to the same object (Topic 3.6).

Step 2, average (lines 16–24), sums and divides (4.10.1). 12 + 15 + 15 + 20 + 9 = 71, and 71.0 / 5 is 14.2. Running this step after the cleanup matters: with the two -1s still in, the average would be wrong.

Step 3, aboveAverage (lines 26–37), builds a filtered list (4.10.7). It returns a new list holding 15, 15, and 20, the readings greater than 14.2, and leaves readings alone.

Step 4, hasRepeatInARow (lines 39–51), checks consecutive pairs (4.10.3). The pair loop stops at i < list.size() - 1. The first pair, 12 and 15, differs; the second, 15 and 15, matches, so the method returns true at once without checking the rest. That early return is an “at least one” check (4.10.2) written without a flag.

Cleaned: [12, 15, 15, 20, 9]
Average: 14.2
Above average: [15, 15, 20]
Repeat in a row: true

Several ArrayList bugs look alike in the code but behave very differently when the program runs. Use this table to go from the symptom back to the cause.

• Array algorithms carry over to ArrayList by using size(), get(i), and set(i, value). Start a minimum or maximum at an element of the list, and remember that an average needs a non-empty list.
• “At least one” flags start false, “all” flags start true, and counters start at 0. None of them is ever switched back inside the loop.
• Pair loops stop at i < size() - 1. Duplicate checks use nested loops with j = i + 1, and Integer elements are unboxed before comparing with ==.
• Inserting at index i moves later elements right, so step past the new element. Deleting at index i moves later elements left, so add 1 only when nothing was removed, or traverse backward. Never change a list’s size inside an enhanced for loop.
• remove and add shift and rotate a list, since remove returns the element it took out. A reverse swaps pairs with a temporary variable and stops at size() / 2.
• A filtered list is built by adding matching elements to a new list, leaving the original unchanged. Collections traversed side by side share one index, bounded so it is valid for every one of them.

import java.util.ArrayList;

public class RemoveThenSum
{
    public static void main(String[] args)
    {
        ArrayList<Integer> changes = new ArrayList<Integer>();
        changes.add(-2);
        changes.add(-3);
        changes.add(5);
        changes.add(-1);
        changes.add(4);

        for (int i = 0; i < changes.size(); i++)
        {
            if (changes.get(i) < 0)
            {
                changes.remove(i);
            }
        }
        int sum = 0;
        for (int change : changes)
        {
            sum += change;
        }
        System.out.println(changes);
        System.out.println("Sum: " + sum);
    }
}

[-3, 5, 4]
Sum: 6

import java.util.ArrayList;

public class InsertNoBoundCheck
{
    public static void insertInOrder(ArrayList<Integer> list, int value)
    {
        int index = 0;
        while (list.get(index) < value)
        {
            index++;
        }
        list.add(index, value);
    }

    public static void main(String[] args)
    {
        ArrayList<Integer> times = new ArrayList<Integer>();
        times.add(10);
        times.add(25);
        times.add(40);
        times.add(55);

        insertInOrder(times, 30);
        System.out.println(times);
        insertInOrder(times, 70);
        System.out.println(times);
    }
}

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 5 out of bounds for length 5

while (index < list.size() && list.get(index) < value)