Implementing ArrayList Algorithms

Welcome, students! 👋 In this lesson, you will learn how to write and reason about algorithms that use ArrayList objects in AP Computer Science A. ArrayList is one of the most important data collections in Java because it stores a list of items that can grow or shrink as needed. That makes it useful for things like a playlist, a shopping cart, a class roster, or a list of game scores 📱🎵🛒

What You Need to Know First

An ArrayList is part of Java’s collection tools. Unlike an array, an ArrayList can change size after it is created. That flexibility is the main reason it is used so often in real programs.

In AP Computer Science A, you need to know how to work with ArrayList algorithms such as:

traversing the list
adding items in the correct position
removing items safely
searching for a value
modifying items based on a condition
comparing ArrayList methods with array methods

A key idea is that ArrayList elements are accessed with indexes, starting at $0$. If a list has $n$ elements, the valid indexes are from $0$ to $n-1$.

Example: if scores stores $[88, 92, 75]$, then scores.get(0) is $88$, scores.get(1) is $92$, and scores.get(2) is $75$.

Core Methods You Should Recognize

The most common ArrayList methods are:

add(value) to append an item to the end
add(index, value) to insert an item at a specific position
get(index) to read an item
set(index, value) to replace an item
remove(index) to delete an item by position
size() to find how many items are in the list
contains(value) to check whether a value appears in the list

These methods are the building blocks for many AP exam questions. Often, the question is not about memorizing a method name alone. It is about understanding what happens to the whole list after the method runs.

Traversing an ArrayList Correctly

Traversal means visiting each element in the list. The most common way is a for loop that uses the indexes from $0$ to size() - 1.

A typical pattern looks like this:

$$\text{for } i = 0; i < \text{list.size()}; i++$$

This pattern is useful when you need the index, such as when removing, replacing, or inserting items.

Example: suppose names contains ["Ava", "Ben", "Cara"]. A traversal can print each name or check each name against a condition.

A for-each loop is also useful when you only need the values, not the indexes:

for (String name : names) {
    System.out.println(name);
}

However, be careful: if you need to remove items while traversing, a for-each loop is not the right tool. That can cause errors because the list changes during the loop.

Why Index-Based Traversal Matters

Many ArrayList algorithms require index-based logic. For example, if you want to replace every negative number with $0$, you need access to each position:

for (int i = 0; i < nums.size(); i++) {
    if (nums.get(i) < 0) {
        nums.set(i, 0);
    }
}

This is a standard AP-style algorithm because it shows how to inspect each element and update the list safely.

Inserting and Removing Items Safely

Adding and removing items is where many students make mistakes. The reason is that when you change an ArrayList, the indexes of later elements can shift.

Suppose items contains ["pen", "pencil", "eraser"].

items.add("marker") makes it ["pen", "pencil", "eraser", "marker"]
items.add(1, "ruler") makes it ["pen", "ruler", "pencil", "eraser"]
items.remove(2) removes the item at index $2$

When you remove an element, everything after it moves left by one position. That means the next item gets the same index as the one that was removed.

The Remove-in-a-Loop Problem

If you are removing items while going through a list, you must pay attention to index changes.

Example: remove all even numbers from [2, 4, 6, 7].

If you use a normal increasing loop and remove index $0$, the list becomes [4, 6, 7]. Now the next element, $4$, has moved into index $0$. If the loop moves to index $1$, it may skip $4$.

One safe pattern is to loop backward:

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

This works because removing items from the end does not affect indexes that have not been visited yet.

Another common solution is to use a while loop and only increase the index when no removal happens.

Searching Through an ArrayList

Searching means finding whether a value exists and, sometimes, where it is located. The simplest search algorithm is a linear search, which checks each item one by one until it finds the target or reaches the end.

Example: if scores is [65, 71, 84, 71] and you want to know whether $71$ is present, a linear search checks items until it finds $71$.

A typical search algorithm is:

int index = -1;
for (int i = 0; i < list.size(); i++) {
    if (list.get(i).equals(target)) {
        index = i;
        break;
    }
}

If the target is not found, index stays $-1$. That is a common way to show failure in AP Computer Science A.

Why `.equals()` Matters

For objects like String, you should use .equals() instead of == when comparing values. For example, "cat".equals(name) checks whether two strings have the same characters. Using == compares references, which is not the same thing.

This matters a lot for ArrayList<String> and other lists of objects. A correct search depends on correct comparison.

Common AP Algorithms with ArrayLists

AP Computer Science A often asks you to implement or trace algorithms that do one of these tasks:

1. Count Matching Elements

You may need to count how many elements meet a condition.

Example: count how many scores are at least $90$.

int count = 0;
for (int i = 0; i < scores.size(); i++) {
    if (scores.get(i) >= 90) {
        count++;
    }
}

2. Find the Largest or Smallest Value

A common pattern is to start with the first item and compare every other item to it.

int max = scores.get(0);
for (int i = 1; i < scores.size(); i++) {
    if (scores.get(i) > max) {
        max = scores.get(i);
    }
}

3. Shift or Rotate Values

Sometimes you move items around. For example, moving the first item to the end:

String first = names.remove(0);
names.add(first);

4. Filter the List

Filtering means building a new list with only the items you want.

Example: store only passing grades.

ArrayList<Integer> passing = new ArrayList<Integer>();
for (int i = 0; i < grades.size(); i++) {
    if (grades.get(i) >= 70) {
        passing.add(grades.get(i));
    }
}

This is useful when you do not want to destroy the original list.

How This Fits Into Data Collections

ArrayList is part of the bigger topic of Data Collections, which also includes arrays, 2D arrays, searching, sorting, recursion, and data ethics. The main connection is that all these topics help store, organize, and analyze groups of data.

An ArrayList is especially useful when the number of items is not fixed. In real life, a list of messages, favorite songs, or customer orders can change constantly. That is exactly where ArrayList shines.

In AP Computer Science A, you should be able to explain why ArrayList is a good choice for flexible data and how its algorithms compare with array algorithms. Arrays have fixed size, while ArrayList can expand. That difference affects how you design solutions.

Big Exam Idea

When solving a problem, think about:

What data is being stored?
Do I need to add or remove items?
Do I need the indexes?
Do I need to search, count, replace, or filter?

These questions help you choose the correct algorithm and the correct collection.

Conclusion

students, implementing ArrayList algorithms means understanding how to work with lists that can change size. You learned how to traverse a list, search for values, count matches, insert and remove safely, and use indexes without causing errors. These skills are essential in AP Computer Science A because they show how to manage data collections in clear, reliable ways ✅

Remember: the important part is not just knowing the methods. It is knowing how the list changes after each operation and how to write algorithms that stay correct even when the data shifts.

Study Notes

ArrayList stores items in a resizable list.
Indexes start at $0$, and the last index is size() - 1.
Common methods include add, get, set, remove, size, and contains.
Use a standard for loop when you need indexes.
Use for-each when you only need values and are not changing the list.
Removing items shifts later elements left by one index.
A backward loop is often safest when removing multiple items.
Use .equals() to compare object values such as String.
Linear search checks items one at a time.
Common ArrayList algorithms include counting, finding max/min, filtering, rotating, and searching.
ArrayList is a key part of Data Collections because it supports flexible data storage and manipulation.