Welcome to Implementing ArrayList Algorithms!

In the previous chapters, we learned how to create an ArrayList and how to use methods like add, set, and remove. Now, it's time to put those tools to work! In this chapter, we focus on the "logic" of programming—writing algorithms to solve specific problems using the data inside our lists.

Think of an ArrayList like a digital shelf of items. An algorithm is just the set of instructions you follow to find the heaviest item, count how many items are red, or rearrange the items in a different order. Don't worry if this seems tricky at first; most of these algorithms follow the same "recipe" every time!

1. The "Big Three" Algorithms: Sum, Average, and Count

These are the most common tasks you will perform. They almost always involve a traversal (looping through the whole list) and a variable to keep track of your progress.

Calculating a Sum and Average

To find the total of all numbers in an ArrayList of Integer or Double objects:

  1. Create a "running total" variable and initialize it to \(0\).
  2. Use an enhanced for loop (if you don't need indices) to visit every element.
  3. Add each element's value to your total.

Example: To find the average, simply take that final sum and divide it by \(list.size()\). Just remember to use double math to keep the decimal places!

Counting Occurrences

Sometimes you only want to count items that meet a specific condition (e.g., "How many scores are above \(90\)?").

  • Initialize a counter variable to \(0\).
  • Inside your loop, use an if statement to check the condition.
  • Only increment (\(++\)) the counter if the condition is true.

Quick Review: For these algorithms, an enhanced for loop is usually the cleanest choice because you are looking at every item and not changing the list's size.

2. Finding Minimum and Maximum

Finding the largest or smallest value is a classic AP Computer Science A task. There is one "golden rule" to remember here: Initialization matters!

The Algorithm

  1. Create a variable called \(max\) (or \(min\)).
  2. Important: Do NOT initialize \(max\) to \(0\). If your list contains only negative numbers (like \(-5, -10, -15\)), your code would incorrectly say \(0\) is the maximum!
  3. Best Practice: Initialize \(max\) to the very first element in the list: \(list.get(0)\). Alternatively, use \(Integer.MIN_VALUE\) for finding a maximum.
  4. Loop through the list. If you find an element greater than your current \(max\), update \(max\) to be that new value.

Key Takeaway: Think of this like a "King of the Hill" game. The current \(max\) stays the king until a larger number comes along and takes its place.

A Linear Search is a fancy way of saying "looking through the list one by one until you find what you want."

In this chapter, we focus on the basic implementation:

  • Searching for a value: Use a loop to check each element. As soon as you find a match, you can return the index or a boolean \(true\).
  • The "Not Found" case: If the loop finishes and you never found the item, return \(-1\) (for index searches) or \(false\).

Note: More advanced searches, like Binary Search, are covered in a later chapter (Unit 4.14). For now, focus on the simple one-by-one search.

4. Shifting and Reversing Elements

These algorithms actually change the positions of the elements in the ArrayList.

Reversing a List

To flip a list backwards, you have two main strategies:

  1. The "New List" Strategy: Create a second, empty ArrayList. Loop through your original list from the last index down to the first index (\(i--\)), adding each item to the new list.
  2. The "Swap" Strategy: Use a single loop that goes halfway through the list. Swap the element at index \(i\) with the element at the "mirror" index at the end of the list.

Shifting Elements

Shifting means moving everything over by one spot.
• Left Shift: The first element is usually moved to the end, and everything else moves "down" one index.
• Right Shift: The last element is moved to the front, and everything else moves "up" one index.

Common Mistake: When shifting, be careful not to overwrite your data! You usually need to save one element in a temporary variable (a "temp") before you start moving other elements into its spot.

5. Choosing the Right Loop

When implementing these algorithms, choosing the right tool makes the job easier:

Use an Enhanced For Loop when:
• You need to look at every single element.
• You don't care about the index positions.
• You are not adding or removing items.
(Great for: Sum, Average, Count, Max/Min)

Use a Standard For Loop when:
• You need the index (\(i\)).
• You are only looking at part of the list.
• You are moving elements around (shifting/reversing).
• You need to traverse backwards.
(Great for: Searching for an index, Shifting, Reversing)

Did you know? If you try to remove an item from an ArrayList while using an enhanced for loop, Java will crash with a \(ConcurrentModificationException\)! Always use a standard loop or an Iterator if you plan to change the list's size while looping.

Chapter Summary

  • Sum/Average/Count: Use a tracker variable and visit every element.
  • Max/Min: Initialize with the first element, not \(0\).
  • Search: Check elements one-by-one; return \(-1\) or \(false\) if not found.
  • Shifting/Reversing: Use a temporary variable to avoid losing data while moving items.
  • Logic: Choose the loop that matches your goal. If you need indices or are modifying the list, use a standard for loop.