ACSA Exam Prep
Unit 4 · Data Collections · Topic 4.10

Implementing ArrayList Algorithms

Skill 2.BSkill 3.BSkill 3.DSkill 4.A

Big idea: Every array algorithm works on an ArrayList with get and size. Lists also let you insert and delete, which FRQ 3 tests directly.

Learning objectives
  • Develop code for standard and original algorithms for a particular context or specification that involve ArrayList objects and determine the result of these algorithms.

Filtering objects into a new list

Code
ArrayList<Book> books = new ArrayList<Book>();
books.add(new Book("Dune", 412));
books.add(new Book("Holes", 233));
books.add(new Book("Emma", 474));
ArrayList<String> longOnes = new ArrayList<String>();
int pages = 0;
for (Book b : books) {
  pages += b.getPages();
  if (b.getPages() > 400) longOnes.add(b.getTitle());
}
System.out.println(longOnes + " " + pages / books.size());
Output
[Dune, Emma] 373

Inserting in sorted order

Find the first element bigger than the new value and insert there. If none is bigger, the loop ends at size() and the value is appended.

Code
ArrayList<Integer> list = new ArrayList<Integer>(List.of(3, 8, 15));
int value = 10;
int i = 0;
while (i < list.size() && list.get(i) < value) {
  i++;
}
list.add(i, value);
System.out.println(list);
Output
[3, 8, 10, 15]

Working with two collections at once

Parallel traversals walk two lists (or a list and an array) with the same index.

Code
String[] names = {"Ana", "Bo", "Cy"};
ArrayList<Integer> scores = new ArrayList<Integer>(List.of(88, 95, 70));
int bestIndex = 0;
for (int i = 1; i < names.length; i++) {
  if (scores.get(i) > scores.get(bestIndex)) bestIndex = i;
}
System.out.println(names[bestIndex]);
Output
Bo
Key points
  • All array algorithms apply, plus inserting and deleting elements.
  • Some algorithms traverse several Strings, arrays, or ArrayLists at once.
Watch out
  • Use get(i), not [i], with an ArrayList.
  • Put the bounds check first in a while condition (i < list.size() && ...) so short-circuiting prevents an exception.
Quick check
Write the loop header to visit every element of ArrayList<Double> temps by index.
Show answer
for (int i = 0; i < temps.size(); i++)
Practice 4.10 (10 questions)