Unit 4.10: ArrayList Algorithms

Standard ArrayList Algorithms

The same standard algorithms that apply to arrays can also be used with ArrayLists, using methods like get() and size() instead of array syntax.

Common Algorithms (EK 4.10.A.1)

Minimum and Maximum

Initializing & Updating

To find the min or max, initialize a variable with the first element and update it if a smaller (or larger) element is found during traversal.

Task: Finding the maximum value in an ArrayList of integers.

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

Sum, Average, and Counting

Accumulation

Use an accumulator variable (often initialized to 0) to track the sum or count as you iterate through the list.

Task: Calculating the sum, average, and number of passing scores.

double sum = 0;
int countPassing = 0;
for (double s : scores) {
    sum += s;
    if (s >= 80.0) countPassing++;
}
double average = sum / scores.size();

Property Checks (All / At Least One)

Boolean Flagging

Use a boolean flag. For "All", assume true and set to false if a counter-example is found. For "At Least One", assume false and set to true if a match is found.

Task: Checking if all numbers in a list are even.

boolean allEven = true;
for (int n : nums) {
    if (n % 2 != 0) {
        allEven = false;
        break;
    }
}

Accessing Consecutive Pairs

Boundary Management

Access elements at i and i + 1. Ensure the loop terminates at size() - 1 to avoid an IndexOutOfBoundsException.

Task: Detecting if any two adjacent elements are equal.

for (int i = 0; i < list.size() - 1; i++) {
    if (list.get(i).equals(list.get(i + 1))) {
        System.out.println("Consecutive duplicate found!");
    }
}

Duplicate Detection (Anywhere in List)

Nested Comparisons

Use nested loops. The outer loop picks an element at i, and the inner loop checks all subsequent elements at j = i + 1.

Task: Checking for duplicate elements anywhere in the list.

boolean hasDuplicates = false;
for (int i = 0; i < list.size() - 1; i++) {
    for (int j = i + 1; j < list.size(); j++) {
        if (list.get(i).equals(list.get(j))) {
            hasDuplicates = true;
        }
    }
}

Shifting and Reversing

Reordering Elements

Shifting elements involves moving them one position left or right. Reversing involves swapping elements from the outside in until the midpoint is reached.

Task: Reversing a list in-place and shifting elements one position to the left (wrap-around).

// Reversing in-place
for (int i = 0; i < list.size() / 2; i++) {
    int swapIndex = list.size() - 1 - i;
    String temp = list.get(i);
    list.set(i, list.get(swapIndex));
    list.set(swapIndex, temp);
}

// Shifting elements one position to the left (wrap-around)
if (list.size() > 1) {
    String first = list.remove(0);
    list.add(first);
}

Inserting and Deleting

Structural Modification

Use add(index, element) to insert and remove(index) to delete. Remember that these operations shift subsequent elements and change the list size.

Task: Inserting an element at a specific index and removing the last element.

// Inserting "Gold" at index 1
list.add(1, "Gold");

// Deleting the last element
if (list.size() > 0) {
    list.remove(list.size() - 1);
}

Traversing Multiple Data Structures

Some algorithms require traversing multiple String, array, or ArrayList objects simultaneously. This is often done with a single loop that uses the same index to access elements from each data structure.

Index Synchronization

When traversing multiple structures in parallel, ensure they are of the same length. If one is shorter than the other, accessing an index that doesn't exist in the smaller collection will cause an IndexOutOfBoundsException.

Task: Comparing elements of two ArrayLists at the same index.

import java.util.ArrayList;

public class ParallelTraversal {
    public static void main(String[] args) {
        ArrayList<String> list1 = new ArrayList<>();
        list1.add("Apple");
        list1.add("Banana");
        list1.add("Cherry");

        ArrayList<String> list2 = new ArrayList<>();
        list2.add("Apple");
        list2.add("Orange");
        list2.add("Cherry");

        int matchCount = 0;
        
        // We use one index 'i' to look at both lists at once
        for (int i = 0; i < list1.size(); i++) {
            if (list1.get(i).equals(list2.get(i))) {
                matchCount++;
                System.out.println("Match found at index " + i + ": " + list1.get(i));
            }
        }
        
        System.out.println("Total matching elements: " + matchCount);
    }
}