Topic 4.8 — Developing Algorithms Using ArrayLists

Goal: apply common algorithm patterns (searching, counting, replacing, inserting/removing) to ArrayList objects, and understand how shifting affects indexes.

The big idea

ArrayList algorithms look like array algorithms, but you use methods: size(), get, set, add, and remove.

The key difference: inserting/removing shifts elements, changing what lives at each index.

Method toolbox (you’ll see these everywhere)

Action	Method	Notes
size	`list.size()`	count of elements
read	`list.get(i)`	element at index `i`
replace	`list.set(i, x)`	overwrites existing element
append	`list.add(x)`	adds to end
insert	`list.add(i, x)`	shifts right from `i`
remove	`list.remove(i)`	shifts left after `i`

Linear search (find if a target exists)

public static boolean contains(ArrayList<Integer> list, int target) {
  for (int i = 0; i < list.size(); i++) {
    if (list.get(i) == target) return true;
  }
  return false;
}

Count matches

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

Replace values (update in-place)

Use set with an index.

// Replace all negatives with 0
for (int i = 0; i < list.size(); i++) {
  if (list.get(i) < 0) {
    list.set(i, 0);
  }
}

Insert shifts right

Everything at index i and after moves one step to the right.

ArrayList<String> a = new ArrayList<>();
a.add("A");
a.add("C");

a.add(1, "B"); // insert at index 1
// a is now ["A", "B", "C"]

Remove shifts left

Everything after the removed index moves left, shrinking the list.

ArrayList<String> a = new ArrayList<>();
a.add("A");
a.add("B");
a.add("C");

a.remove(1); // removes "B"
// a is now ["A", "C"]

Remove algorithm: do it safely

If you remove while looping forward, you might skip elements because indexes shift. A common safe approach is to loop backward.

// Remove all zeros safely
for (int i = list.size() - 1; i >= 0; i--) {
  if (list.get(i) == 0) {
    list.remove(i);
  }
}

Algorithm pattern: build a new list

Sometimes it’s simpler to create a filtered copy.

ArrayList<Integer> keep = new ArrayList<>();
for (int x : list) {
  if (x != 0) keep.add(x);
}
// keep contains all non-zero values

Index-based neighbor work

Any neighbor compare needs i < list.size() - 1.

int inc = 0;
for (int i = 0; i < list.size() - 1; i++) {
  if (list.get(i) < list.get(i + 1)) inc++;
}

Quick self-check

What’s the last valid index in a list of size n?
What does add(i, x) do to the elements already in the list?
Why can removing while looping forward skip elements?
Write code to replace all values < 5 with 5.
Write a safe loop to remove all negative values.

← Back to Unit 4 topics