4.10 Implementing ArrayList Algorithms

4.10 Implementing ArrayList Algorithms

An ArrayList algorithm turns a stored collection of objects into useful information: pair competitors, find the highest score, count qualifying entries, or identify a particular object.

From stored objects to meaningful results

A user-made class defines the objects being stored. An ArrayList then acts like an expandable roster, inventory, or collection of records. The important design step is not merely putting objects into the list; it is writing methods that process those objects.

Topic 4.10 — Implementing ArrayList Algorithms: Design algorithms that operate on objects stored in an ArrayList, usually by combining list access, traversal, selection, object construction, and return values.

A strong case study includes three connected layers:

1. A user-made class, such as Competitor, Book, or Word.
2. Methods that store objects in an ArrayList.
3. Methods that traverse the list and perform algorithms such as searching, counting, finding an extreme value, or constructing a new collection.

The computational thinking practices are especially visible here:

• Computational Thinking Practice 1 — Design Code: Decide what each method should accomplish and what data it must inspect.
• Computational Thinking Practice 2 — Develop Code: Write the ArrayList operations and control structures.
• Computational Thinking Practice 3 — Analyze Code: Trace indexes, list sizes, conditions, and returned objects.
• Computational Thinking Practice 4 — Document Code and Computing Systems: Explain the purpose and assumptions of each algorithm.
• Computational Thinking Practice 5 — Use Computers Responsibly: Consider whether the stored data and resulting decisions are appropriate and fair.

Worked case study: pairing competitors

Suppose competitorList stores Competitor objects. The method buildMatches() must create pairings and return them as an ArrayList<Match>. It does not modify the original competitor list; instead, it constructs a separate list of match objects.

public ArrayList<Match> buildMatches()
{
  ArrayList<Match> matches = new ArrayList<Match>();

  if (competitorList.size() % 2 == 0)
  {
    for (int i = 0; i < competitorList.size() / 2; i++)
    {
      matches.add(new Match(
        competitorList.get(i),
        competitorList.get(competitorList.size() - i - 1)
      ));
    }
  }
  else
  {
    for (int i = 1; i < competitorList.size() / 2 + 1; i++)
    {
      matches.add(new Match(
        competitorList.get(i),
        competitorList.get(competitorList.size() - i)
      ));
    }
  }

  return matches;
}

The first statement creates a new empty list:

ArrayList<Match> matches = new ArrayList<Match>();

Each successful pairing is then added with .add(). The expression new Match(...) creates a Match object from two Competitor objects, and .add() stores that object in matches.

Why the even and odd cases differ

The condition

competitorList.size() % 2 == 0

tests whether the number of competitors is even. The remainder operator % produces 0 when the size divides evenly by 2.

For an even-sized list, the algorithm pairs opposite ends:

Iteration	First index	Second index
i = 0	0	size - 1
i = 1	1	size - 2
i = 2	2	size - 3

If the list contains six competitors, the pairs are formed from indexes (0, 5), (1, 4), and (2, 3). The loop stops after size / 2 iterations because every competitor has been used exactly once.

For an odd-sized list, the code begins at i = 1, deliberately skipping index 0. With five competitors, it creates pairs using indexes (1, 4) and (2, 3), leaving the first competitor unpaired. This is a design decision built into the algorithm, not an accidental omission.

Combining several ArrayList algorithms

A complete case study should perform at least three algorithms from Topic 4.5, Implementing Array Algorithms, adapted for objects. For a list of Competitor objects, possible methods include:

• Find the competitor with the greatest score.
• Compute the total or average score.
• Count competitors satisfying a condition.
• Search for a competitor with a particular name.
• Create a new list containing only qualifying competitors.

Each algorithm follows the same engineering pattern: establish an initial result, traverse relevant elements, update the result when a condition is met, and return the final value or collection. When the result is an object, initialize carefully—for example, use the first list element as the current best rather than inventing a meaningless default object.

Word Search Creator Lab

The Word Search Creator Lab applies this design to words and placements. Its constructor or setup method uses .add() to populate an ArrayList, while later methods traverse the stored data and apply algorithms to create or inspect the word-search structure.

Misconception check: Calling .add() does not replace an existing element. It appends an element and increases the list’s size() by $1$. Replacement requires .set(index, value).

Another frequent error is confusing an object’s position with the object itself. competitorList.get(i) returns the object at index i; i alone is only an integer index. Similarly, competitorList.size() is a count, while the last valid index is competitorList.size() - 1.

Retrieval check

A list contains seven competitors. In the odd-size branch, which competitor is skipped, how many Match objects are created, and why does the loop begin with i = 1?

Answer: Index 0 is skipped, three Match objects are created, and starting at i = 1 pairs the remaining six competitors from opposite ends without using the skipped competitor.