Unit 4: Data Collections

4.1 Arrays — Creation and Access

An array is a fixed-size sequence of values of the same type. Indexed starting at 0.

Three ways to make an array

// 1. Empty array of given size (filled with defaults: 0, 0.0, false, null)
int[] nums = new int[5];

// 2. Initializer list — size inferred from contents
int[] scores = {95, 87, 73, 100, 65};

// 3. Long form
int[] grades = new int[]{95, 87, 73};

Accessing elements

arr[i] — element at index i (read or write)
arr.length — number of elements (no parentheses — it's a field, not a method)

✏️ Your turn — first array

Build int[] scores = {95, 87, 73, 100, 65};, then:

Print its length
Print the first element using scores[0]
Print the last element using scores.length - 1
Change index 1 to 90 and print scores[1] to confirm

Show solution

public class Main {
    public static void main(String[] args) {
        int[] scores = {95, 87, 73, 100, 65};
        System.out.println(scores.length);
        System.out.println(scores[0]);
        System.out.println(scores[scores.length - 1]);

        scores[1] = 90;
        System.out.println(scores[1]);
    }
}

🚨 String.length() vs array.length

Strings use length() (a method, with parens). Arrays use length (a field, no parens). Easy to mix up.

4.2 Traversing Arrays with a for Loop

The standard pattern: index from 0 to length - 1.

✏️ Your turn — three traversals

With int[] nums = {3, 8, 2, 9, 4};, write three separate indexed for-loops:

Print each element with label: nums[0] = 3, nums[1] = 8, …
Compute the sum and print Sum = 26
Print the elements in reverse on one line: 4 9 2 8 3

Show solution

public class Main {
    public static void main(String[] args) {
        int[] nums = {3, 8, 2, 9, 4};
        for (int i = 0; i < nums.length; i++) {
            System.out.println("nums[" + i + "] = " + nums[i]);
        }
        int sum = 0;
        for (int i = 0; i < nums.length; i++) sum += nums[i];
        System.out.println("Sum = " + sum);

        for (int i = nums.length - 1; i >= 0; i--) {
            System.out.print(nums[i] + " ");
        }
    }
}

4.3 Enhanced for Loop (for-each)

When you don't need the index, this is cleaner:

for (type variable : array) {
    // use variable, which holds the current element
}

✏️ Your turn — for-each

Sum the elements of int[] nums = {3, 8, 2, 9, 4}; using an enhanced for-loop (no index variable), and print Sum = 26.

Show solution

public class Main {
    public static void main(String[] args) {
        int[] nums = {3, 8, 2, 9, 4};
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }
        System.out.println("Sum = " + sum);
    }
}

⚠ Can't modify the array

The variable in a for-each is a copy for primitives. Writing n = 0 inside the loop does NOT change the array. Use an indexed for-loop when you need to write to elements.

4.4 Standard Array Algorithms

Memorize these patterns. They appear constantly on multiple-choice and FRQs.

Find max

✏️ Your turn — max

Write a static method max(int[] arr) that returns the largest element. Start best at arr[0], then scan from index 1 upward. Test with {3, 9, 1, 7, 2} → 9.

Show solution

public static int max(int[] arr) {
    int best = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > best) best = arr[i];
    }
    return best;
}

Count matches

✏️ Your turn — countEvens

Write countEvens(int[] arr) that returns how many elements are even. Use a for-each. Test with {1,2,3,4,5,6} → 3.

Show solution

public static int countEvens(int[] arr) {
    int count = 0;
    for (int n : arr) {
        if (n % 2 == 0) count++;
    }
    return count;
}

Average

✏️ Your turn — average

Write average(int[] arr) that returns the average as a double. Watch out: sum / arr.length with both ints is integer division — cast at least one to double first. Test with {10,20,30,40,50} → 30.0.

Show solution

public static double average(int[] arr) {
    int sum = 0;
    for (int n : arr) sum += n;
    return (double) sum / arr.length;
}

Shift elements left (overwriting first)

✏️ Your turn — shift left

Given {1, 2, 3, 4, 5}, shift every element one to the left so the array becomes {2, 3, 4, 5, 5} (the last element is duplicated). Loop i from 0 to length - 2 and set arr[i] = arr[i+1]. Then print the array space-separated.

Show solution

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        for (int i = 0; i < arr.length - 1; i++) {
            arr[i] = arr[i + 1];
        }
        for (int n : arr) System.out.print(n + " ");   // 2 3 4 5 5
    }
}

4.5 ArrayList — Resizable Arrays

An ArrayList is like an array, but it can grow and shrink. It holds objects, not primitives — so use the wrapper classes (Integer, Double).

import java.util.ArrayList;

ArrayList<Integer> nums = new ArrayList<Integer>();
ArrayList<String>  names = new ArrayList<>();   // shorthand <> on right

📘 The diamond operator <>

The type inside <...> on the right is optional — Java infers it from the left. Use the diamond form (<>) for cleaner code.

✏️ Your turn — first ArrayList

Import java.util.ArrayList, then create an empty ArrayList<String> called names with the diamond operator. Add "Anita", "Ben", then "Carla". Print:

The whole list (should look like [Anita, Ben, Carla])
Its size
The element at index 1

Show solution

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<String> names = new ArrayList<>();
        names.add("Anita");
        names.add("Ben");
        names.add("Carla");
        System.out.println(names);
        System.out.println(names.size());
        System.out.println(names.get(1));
    }
}

4.6 ArrayList Methods to Memorize

Method	What it does
`size()`	Returns number of elements (uses `()`, unlike array.length!)
`add(x)`	Appends `x` at the end
`add(i, x)`	Inserts `x` at index `i`, shifting others right
`get(i)`	Returns element at index `i`
`set(i, x)`	Replaces element at index `i` with `x`, returns old value
`remove(i)`	Removes element at index `i`, returns it, shifts others left

✏️ Your turn — every ArrayList method

Build an ArrayList<Integer> step by step. After each operation, the list should be:

add(10) → [10]
add(20) → [10, 20]
add(30) → [10, 20, 30]
add(1, 15) → [10, 15, 20, 30]
set(0, 5) → [5, 15, 20, 30]
remove(2) → [5, 15, 30]

Then print the final list and its size.

Show solution

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<>();
        nums.add(10);
        nums.add(20);
        nums.add(30);
        nums.add(1, 15);
        nums.set(0, 5);
        nums.remove(2);
        System.out.println(nums);     // [5, 15, 30]
        System.out.println(nums.size());
    }
}

🚨 Remove during a loop = bug

Removing while iterating shifts indices and skips elements. If you must remove items in a loop, iterate backwards, or use a while-loop and only increment when you don't remove.

✏️ Your turn — remove safely

Add 2, 3, 4, 5, 6 to an ArrayList<Integer>. Then remove every even element by iterating backwards (from size() - 1 down to 0). Print the result — should be [3, 5].

Try this with a forward loop after and see what bug appears.

Show solution

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> nums = new ArrayList<>();
        nums.add(2); nums.add(3); nums.add(4); nums.add(5); nums.add(6);

        for (int i = nums.size() - 1; i >= 0; i--) {
            if (nums.get(i) % 2 == 0) nums.remove(i);
        }
        System.out.println(nums);   // [3, 5]
    }
}

4.7 ArrayList Algorithms

Same patterns as arrays, but use .size() and .get(i).

Sum of an ArrayList<Integer>

✏️ Your turn — sum (ArrayList)

Write sum(ArrayList<Integer> list) that returns the total. A for-each works on ArrayList too. Test by adding 10, 20, 30 — answer should be 60.

Show solution

public static int sum(ArrayList<Integer> list) {
    int total = 0;
    for (int n : list) total += n;
    return total;
}

Insert in sorted order

✏️ Your turn — insertSorted

Write insertSorted(ArrayList<Integer> list, int x) that inserts x into an already-sorted list so the list stays sorted. Algorithm: scan the list; the first time you see an element ≥ x, insert x at that index and return. If you reach the end, just add(x).

Test by starting with [2, 5, 9] and inserting 4, 11, 1. Should end with [1, 2, 4, 5, 9, 11].

Show solution

public static void insertSorted(ArrayList<Integer> list, int x) {
    for (int i = 0; i < list.size(); i++) {
        if (x <= list.get(i)) {
            list.add(i, x);
            return;
        }
    }
    list.add(x);
}

4.8 Searching: Linear & Binary

Linear search — O(N)

Walk the array, check each element. Works on any array, sorted or not.

✏️ Your turn — linear search

Write linearSearch(int[] arr, int target) that returns the index of target, or -1 if not found. Test: {3, 7, 1, 9, 4, 8} with target 9 → 3; target 5 → -1.

Show solution

public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

Binary search — O(log N)

Requires a sorted array. Repeatedly halve the range. Cuts the search space in half each step.

✏️ Your turn — binary search

Write binarySearch(int[] arr, int target) using two pointers low and high. While low <= high:

Compute mid = (low + high) / 2
If arr[mid] == target, return mid
If arr[mid] < target, search right half (low = mid + 1)
Otherwise, search left half (high = mid - 1)

Return -1 if not found. Test with {1,3,5,7,9,11,13,15}: target 7 → 3; target 10 → -1.

Show solution

public static int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) low  = mid + 1;
        else                   high = mid - 1;
    }
    return -1;
}

💡 Big-O intuition

An array of a million items needs at most ~20 binary-search steps (log₂ 1,000,000 ≈ 20). Linear search would need a million. This is why we sort.

4.9 Sorting: Selection, Insertion & Merge

Selection sort — O(N²)

Find the smallest, swap to position 0. Find the next smallest, swap to position 1. Repeat.

✏️ Your turn — selection sort

Write selectionSort(int[] arr). For each i from 0 to length - 2:

Find minIdx, the index of the smallest element in arr[i..length-1]
Swap arr[i] and arr[minIdx]

Test on {5, 2, 8, 1, 9, 3} → prints 1 2 3 5 8 9.

Show solution

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIdx]) minIdx = j;
        }
        int tmp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = tmp;
    }
}

Insertion sort — O(N²) worst, fast on nearly-sorted data

Build up the sorted region one element at a time. For each new element, shift bigger ones right to make room.

✏️ Your turn — insertion sort

Write insertionSort(int[] arr). For each i from 1 upward:

Save val = arr[i]
Walk j = i - 1 backwards, shifting each arr[j] > val right one
Place val at arr[j + 1]

Same test array.

Show solution

public static void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int val = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > val) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = val;
    }
}

Merge sort — O(N log N)

Divide-and-conquer: split the array in half, sort each half recursively, then merge. Much faster on large inputs.

✏️ Your turn — merge sort

Implement two methods:

mergeSort(int[] arr) — if length < 2, return; otherwise split into left and right halves, recurse on each, then call merge.
merge(int[] arr, int[] left, int[] right) — walk indices i, j, k; copy the smaller of left[i]/right[j] into arr[k], then drain whichever side has leftovers.

Test on {5, 2, 8, 1, 9, 3, 7, 4} → 1 2 3 4 5 7 8 9.

Show solution

public static void mergeSort(int[] arr) {
    if (arr.length < 2) return;
    int mid = arr.length / 2;
    int[] left  = new int[mid];
    int[] right = new int[arr.length - mid];
    for (int i = 0; i < mid; i++) left[i] = arr[i];
    for (int i = mid; i < arr.length; i++) right[i - mid] = arr[i];

    mergeSort(left);
    mergeSort(right);
    merge(arr, left, right);
}

public static void merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) arr[k++] = left[i++];
        else                     arr[k++] = right[j++];
    }
    while (i < left.length)  arr[k++] = left[i++];
    while (j < right.length) arr[k++] = right[j++];
}

Algorithm	Best	Worst	Notes
Selection	O(N²)	O(N²)	Always slow; always N² swaps even on sorted input
Insertion	O(N)	O(N²)	Fast on nearly-sorted data
Merge	O(N log N)	O(N log N)	Recursive; needs extra space

4.10 2D Arrays

A 2D array is an array of arrays — a grid with rows and columns.

int[][] grid = new int[3][4];        // 3 rows, 4 columns

int[][] table = {                     // initializer list
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
};

table.length         // number of rows (3)
table[0].length      // number of cols in row 0 (3)
table[row][col]      // access

Row-major traversal

Outer loop = row, inner loop = column. This is the standard.

✏️ Your turn — row-major traversal

With the 3×3 table {{1,2,3},{4,5,6},{7,8,9}}, print it as a grid using nested for-loops:

1 2 3
4 5 6
7 8 9

Outer loop = rows, inner loop = columns within that row.

Show solution

for (int r = 0; r < table.length; r++) {
    for (int c = 0; c < table[r].length; c++) {
        System.out.print(table[r][c] + " ");
    }
    System.out.println();
}

Column-major traversal

Swap the loop order:

✏️ Your turn — column-major traversal

Same table, but loop columns on the outside and rows on the inside. Output:

1 4 7
2 5 8
3 6 9

Show solution

for (int c = 0; c < table[0].length; c++) {
    for (int r = 0; r < table.length; r++) {
        System.out.print(table[r][c] + " ");
    }
    System.out.println();
}

Enhanced for over 2D

✏️ Your turn — for-each over 2D

Sum every value in the 3×3 table using nested for-each loops (outer over rows, inner over each int in the row). Print Sum: 45.

Show solution

for (int[] row : table) {
    for (int n : row) sum += n;
}

💡 Common 2D pattern

For each row, do a 1D computation (max, min, sum, count). Then collect results into a 1D answer. This decomposition almost always works.

4.11 Recursion

A recursive method calls itself. Every recursive method needs two parts:

Base case — when to stop, returns directly
Recursive case — calls itself on a smaller problem

🚨 No base case → StackOverflowError

Without a base case, the calls never stop. Each call uses memory on the call stack; eventually Java crashes.

Classic: factorial

✏️ Your turn — factorial

Write recursive factorial(int n):

Base case: n <= 1 returns 1
Recursive case: n * factorial(n - 1)

Test: factorial(5) → 120, factorial(10) → 3628800.

Show solution

public static int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Classic: sum of array

✏️ Your turn — recursive array sum

Write arraySum(int[] arr, int start) that returns the sum of arr[start..end]. Base case: start >= arr.length → 0. Recursive case: arr[start] + arraySum(arr, start + 1). Test with {1,2,3,4,5} starting at 0 → 15.

Show solution

public static int arraySum(int[] arr, int start) {
    if (start >= arr.length) return 0;
    return arr[start] + arraySum(arr, start + 1);
}

Classic: reverse a String recursively

✏️ Your turn — recursive reverse

Write reverse(String s) recursively. Base case: length <= 1 returns s. Recursive case: reverse(s.substring(1)) + s.substring(0, 1). Test: reverse("hello") → olleh.

Show solution

public static String reverse(String s) {
    if (s.length() <= 1) return s;
    return reverse(s.substring(1)) + s.substring(0, 1);
}

Recursive binary search

✏️ Your turn — recursive binary search

Write bsearch(int[] arr, int target, int low, int high). Base case: low > high → return -1. Compute mid; if match return it; if too low recurse on right half; else recurse on left half. Test with {1,3,5,7,9,11,13} looking for 9 → 4.

Show solution

public static int bsearch(int[] arr, int target, int low, int high) {
    if (low > high) return -1;
    int mid = (low + high) / 2;
    if (arr[mid] == target) return mid;
    if (arr[mid] < target)  return bsearch(arr, target, mid + 1, high);
    else                    return bsearch(arr, target, low, mid - 1);
}

📘 AP exam expectations

You won't be asked to write recursive code from scratch on multiple-choice, but you must trace it. Practice mentally unwinding the call stack.

4.12 Ethics & Data Collection

The AP exam includes short questions about ethical use of computing. Key topics:

Intellectual property — code is copyrighted. Open-source licenses (MIT, GPL, Apache) define what you may do with someone else's code.
Privacy & PII — personally identifiable information (names, addresses, SSNs) requires careful handling and user consent.
Algorithmic bias — ML models trained on biased data perpetuate bias. Always consider who benefits and who is harmed.
Plagiarism — copying others' code without attribution is academic dishonesty.
Digital divide — uneven access to tech creates social inequality.
Consent & transparency — users should know what data you collect and why.

📘 Exam tip

These questions are common-sense. Pick the answer that respects user autonomy, privacy, and intellectual property. Avoid choices that hide information from users or take their data without consent.

🎯 Unit 4 Review Quiz

1. Given int[] arr = {10, 20, 30, 40};, what is arr[arr.length - 1]?

A 10

B 30

C 40

D Exception

2. Which is true about ArrayList vs array?

A ArrayList can hold any primitive directly

B Arrays can grow dynamically

C ArrayList resizes; arrays are fixed-size

D ArrayList uses 1-based indexing

3. Binary search requires which property of the array?

A Size must be a power of 2

B Must be sorted

C Must contain unique values

D Must contain only positive integers

4. What does factorial(4) return for this method?

public static int factorial(int n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

A 4

B 24

C 120

D StackOverflow

5. For 2D array int[][] g = {{1,2},{3,4},{5,6}};, what is g.length and g[0].length?

A 3, 2

B 2, 3

C 6, 6

D 2, 2

← Unit 3 Next: FRQ Practice →