Data Collections

Programs that gather data raise questions of privacy 隐私 and consent 同意. Collect only what is needed, protect it, and be honest about its use. Data can carry bias 偏见 if it does not represent everyone fairly, leading to unfair results – a responsibility that comes with storing information.

A single variable 变量 holds one value; real problems need to store many related values – a class roster, pixels, sensor readings. A data structure 数据结构 organizes a collection so we can store, find, and process items efficiently. The AP course uses three: the array, the ArrayList, and the 2D array.

An array 数组 is a fixed-size, ordered collection of same-type values. Indices 索引 run from 0 to length - 1:

int[] nums = new int[5];        // five zeros
int[] vals = {3, 1, 4, 1, 5};   // initialized
int first = vals[0];            // 3
int n = vals.length;            // 5 (a field, not a method)

Accessing an index outside 0..length-1 throws an ArrayIndexOutOfBoundsException.

Worked example. For int[] vals = {3, 1, 4, 1, 5};:

new int[5] fills the array with 0; new double[5] with 0.0, new boolean[5] with false and new String[5] with null. An array's size cannot change once it is made.

Traverse 遍历 an array with a for loop (gives the index) or an enhanced for / for-each loop (gives each value, read-only):

for (int i = 0; i < a.length; i++) { a[i] *= 2; }   // can modify
for (int v : a) { System.out.println(v); }          // read each value

Common mistake. An enhanced for loop gives a copy of each value, so this changes nothing in the array:

int[] a = {1, 2, 3};
for (int v : a) {
    v *= 2;        // doubles the copy v only
}
// a is still {1, 2, 3}

To change the elements, use the index loop: a[i] *= 2;. Use an index loop also when the position matters, such as comparing a[i] with a[i + 1]; then stop at i < a.length - 1.

Master these patterns: compute a sum or average, find the max/min, count items meeting a condition, check for a duplicate 重复项, and reverse or shift elements 元素. Each is a traversal with a running result:

int sum = 0;
for (int v : a) sum += v;
double avg = (double) sum / a.length;

Worked example. Reverse an array in place by swapping from both ends.

for (int i = 0; i < a.length / 2; i++) {
    int temp = a[i];
    a[i] = a[a.length - 1 - i];
    a[a.length - 1 - i] = temp;
}

a.length / 2 is 2, so the middle element stays put. Looping to a.length would swap every pair twice and put the array back as it was. A swap needs temp: a[i] = a[j]; a[j] = a[i]; loses the old a[i].

File and IOException live in java.io, so a program that reads a file needs import java.io.*; as well as import java.util.Scanner; for the Scanner. Opening a file can fail (it might not exist), and Java forces you to handle that – the simplest way is to add throws IOException to the method header 方法头. A Scanner then reads the file line by line, using hasNext... to test before reading:

import java.io.*;
import java.util.Scanner;
...
public static void readFile() throws IOException {
    Scanner f = new Scanner(new File("data.txt"));
    while (f.hasNextLine()) {
        String line = f.nextLine();
    }
}

Reading typed tokens 标记 with nextInt(), nextDouble(), or nextBoolean() throws an InputMismatchException if the next token is the wrong type – for example calling nextInt() when the next thing in the file is the word cat.

An ArrayList stores objects 对象, not primitives 基本类型, so a primitive is wrapped in an object: Integer wraps int, Double wraps double. Java does this with autoboxing 自动装箱 (int to Integer) and unboxing 自动拆箱 (back again) automatically, so you can write list.add(5) and int x = list.get(0).

An ArrayList 动态数组 grows and shrinks as you add or remove items. Declare it with the element type in <>:

ArrayList<String> names = new ArrayList<String>();
names.add("Amy");           // append
names.add(0, "Bob");        // insert at index
names.get(0);               // read
names.set(1, "Cara");       // replace
names.remove(0);            // delete, shifts the rest left
names.size();               // count (a method, unlike array.length)

Worked example. The list after each call above:

Indexes must be from 0 to size() - 1, except that add(index, x) also accepts size(), adding at the end; any other index throws an IndexOutOfBoundsException.

Traverse with an index loop or a for-each loop, just like arrays (use size() and get(i)):

for (int i = 0; i < list.size(); i++) { ... list.get(i) ... }
for (String s : list) { ... }

Exam skill: when removing items in an index loop, either loop backwards or do not increment i after a removal – otherwise removing shifts elements left and you skip one. And never add or remove elements while traversing an ArrayList with a for-each loop: changing its size mid-loop throws a ConcurrentModificationException, so use an index loop (backwards, as above) whenever you must remove.

The same algorithms 算法 as arrays – max/min, count, sum – plus insertion and deletion that arrays cannot do easily. A common task is to remove all elements matching a condition, handling the index-shift carefully.

Worked example. Remove every even number from nums, which holds [2, 4, 5, 6].

A forward loop with i++ after every pass goes wrong:

The 4 slid into index 0 after the first removal and was never checked. Looping backwards avoids this, because removing shifts only elements already checked:

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

This leaves [5].

A 2D array 二维数组 is a grid (rows and columns) – an array of arrays:

int[][] grid = new int[3][4];   // 3 rows, 4 columns
grid[r][c] = 7;                 // row r, column c
int rows = grid.length;         // 3
int cols = grid[0].length;      // 4

Visit every cell with nested loops 嵌套循环 – the outer over rows, the inner over columns (row-major order 行主序):

for (int r = 0; r < grid.length; r++)
    for (int c = 0; c < grid[0].length; c++)
        System.out.print(grid[r][c]);

To go column by column (column-major order), swap the loops: the outer over c < grid[0].length, the inner over r < grid.length, still writing grid[r][c]. A common mistake is to use grid.length as the column limit: in a 3 × 4 grid that skips column 3, and in a 4 × 3 grid it throws an ArrayIndexOutOfBoundsException.

Typical grid tasks: sum a row or column, find the max in the grid, count matching cells, or sum a diagonal (where r == c). Each is a nested traversal with a running result.

Worked example. Find the sum of each column of

int[][] m = { {1, 2, 3},
              {4, 5, 6} };

for (int c = 0; c < m[0].length; c++) {
    int colSum = 0;                  // reset for each column
    for (int r = 0; r < m.length; r++) {
        colSum += m[r][c];
    }
    System.out.print(colSum + " ");
}

The outer loop picks a column, the inner loop goes down it: $1 + 4 = 5$, $2 + 5 = 7$, $3 + 6 = 9$, so the output is 5 7 9. colSum is set to 0 inside the outer loop; declared before both loops, it would print the running totals 5 12 21. The main diagonal of a square grid needs only one loop: sum += g[i][i];.

• Linear search 线性搜索 checks each element in turn – works on any list, taking up to $n$ steps.
• Binary search 二分搜索 works only on a sorted 已排序 list: check the middle, then discard the half that cannot contain the target, repeating. It takes about $\log_2 n$ steps – far faster on large data.

int lo = 0, hi = a.length - 1;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (a[mid] == target) return mid;
    else if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}

Exam skill: binary search requires sorted data; know how many comparisons it makes and how lo, hi, mid update.

Worked example. Search for target = 40 in the sorted array {3, 9, 14, 23, 31, 42, 55} (indices 0–6). Start lo=0, hi=6:

• mid = (0+6)/2 = 3, a[3]=23 < 40, so lo = 4;
• mid = (4+6)/2 = 5, a[5]=42 > 40, so hi = 4;
• mid = (4+4)/2 = 4, a[4]=31 < 40, so lo = 5;
• now lo (5) > hi (4), so the loop ends – 40 is not present.

Each step halved the range, so even this miss took only three comparisons.

• Selection sort 选择排序 repeatedly finds the smallest remaining element and swaps it into place.
• Insertion sort 插入排序 grows a sorted front, inserting each new element where it belongs.

Both are simple and take about $n^2$ steps on average – fine for small arrays. Be able to trace the array after each pass.

Recursion 递归 is a method that calls itself on a smaller input. It needs a base case 基本情况 that stops the calls, and a recursive case 递归情形 that moves toward the base:

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

Deep recursion without a reachable base case can cause a stack overflow 栈溢出.

Recursion and iteration are interchangeable. Any recursive solution can be rewritten with a loop (an iterative 迭代的 approach), and any loop can be rewritten with recursion - they solve the same problems. The factorial above is identical in effect to an iterative version:

public static int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) result *= i;   // same answer, no self-call
    return result;
}

So the choice is about clarity, not capability: recursion reads naturally for problems with a self-similar structure (trees, merge sort), while iteration avoids the memory cost of stacking a call frame per step. The exam may ask you to convert one into the other.

Recursion powers efficient algorithms. Binary search can be written recursively (search the correct half). Merge sort 归并排序 splits the array in half, sorts each half recursively, then merges the two sorted halves – taking about $n\log_2 n$ steps, much faster than selection or insertion sort on large data.

Worked example. Trace factorial(4). Each call defers to a smaller one: factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = 4 * 3 * 2 * factorial(1). factorial(1) hits the base case and returns 1, so the calls unwind inward: 2 * 1 = 2, then 3 * 2 = 6, then 4 * 6 = 24. Writing each call above its returned value is the reliable way to trace recursion.

Exam skill: trace a recursive method by writing out each call and its return value, and know that merge sort's efficiency ($n\log n$) beats the $n^2$ simple sorts.

• Weigh both benefits and harms of collecting data — this unit is tested through short written justification, not code.
• Protect personally identifiable information (PII) 个人身份信息 and explain privacy and security risks in context.
• Name real harms: data breaches, surveillance, and algorithmic bias from unrepresentative data.
• Respect intellectual property and licensing when you reuse code or data.
• Give a specific, reasoned answer — a vague "it could be bad" earns no marks.