Unit 4 — Data Collections

Ethical and Social Issues Around Data Collection

As programs increasingly collect, store, and process data about real people, writing code well isn't the only responsibility — how that data is gathered and used matters too.

• Privacy: collecting more personal data than a program actually needs increases risk if that data is ever leaked or misused.
• Bias: a data set that isn't representative of the population it's meant to describe can produce systematically unfair results, even without any "biased" code — the bias comes from what was (or wasn't) collected.
• Security: stored data can be stolen in a breach; encrypting sensitive data and limiting who/what can access it reduces that risk.
• Consent and transparency: people generally have the right to know what data is collected about them and how it will be used.

Introduction to Using Data Sets

So far, each variable has held exactly one value. Many real problems involve working with a whole collection of related values — a class's worth of grades, a week of temperatures — which is awkward and inflexible to represent with separate individually-named variables.

// awkward: doesn't scale, and the count is fixed in the code itself
int grade1 = 88, grade2 = 92, grade3 = 79;

// scales to any amount of data, and the count can vary at runtime
int[] grades = {88, 92, 79};

Java offers a few structures for this, covered across this unit: arrays (fixed size, fast, simple), ArrayLists (resizable, more flexible), and 2D arrays (grids of data, like a table).

Array Creation and Access

An array is a fixed-size, ordered collection of values of the same type, stored under one variable name.

int[] scores = new int[5];      // 5 ints, all default to 0
scores[0] = 88;
scores[1] = 92;

int[] literal = {88, 92, 79};   // declare + fill in one step

System.out.println(literal[0]);       // 88 — indices start at 0
System.out.println(literal.length);   // 3 — length is a field, no parentheses

• Indices run from 0 to length - 1. Accessing array[length] or any negative index throws an ArrayIndexOutOfBoundsException.
• An array's size is fixed once created — you can't add or remove slots, only change the values already in them.
• .length (no parentheses) gives the size — different from String's .length() method (1.15).

Array Traversals

A traversal visits every element of an array, usually with a loop. Java offers two common styles:

// standard for loop — gives you the index
for (int i = 0; i < scores.length; i++) {
    System.out.println("Index " + i + ": " + scores[i]);
}

// enhanced for loop ("for-each") — simpler when you don't need the index
for (int s : scores) {
    System.out.println(s);
}

Implementing Array Algorithms

The accumulator patterns from 2.9 apply directly to arrays — most array algorithms are a traversal with one small piece of logic added inside.

int[] nums = {4, 9, 2, 7, 5};
int sum = 0, max = nums[0], countOver5 = 0;

for (int n : nums) {
    sum += n;
    if (n > max) max = n;
    if (n > 5) countOver5++;
}
double average = (double) sum / nums.length;

A slightly trickier pattern is shifting elements — e.g. removing an element from an array by shifting everything after it one slot left:

// remove the element at index "index" by shifting later elements left
for (int i = index; i < nums.length - 1; i++) {
    nums[i] = nums[i + 1];
}

Using Text Files

Data sets often start life as a text file rather than values typed directly into code. Java's Scanner (1.4) can read from a File just as easily as from System.in.

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

try {
    Scanner fileIn = new Scanner(new File("scores.txt"));
    while (fileIn.hasNextLine()) {
        String line = fileIn.nextLine();
        System.out.println(line);
    }
    fileIn.close();
} catch (FileNotFoundException e) {
    System.out.println("Could not find the file.");
}

• Reading a file can fail (wrong path, missing file), so it's wrapped in a try/catch block that handles FileNotFoundException.
• hasNextLine() / hasNext() check whether more data remains, so the loop stops cleanly at the end of the file instead of crashing.
• A common pattern: read each line, parse it into the right type, and store it into an array or ArrayList as you go.

Wrapper Classes

Primitive types (int, double, boolean) aren't objects, but some Java features — like ArrayList — only work with objects. Wrapper classes package a primitive value inside an object.

Integer boxed = 5;         // autoboxing: int -> Integer, automatic
int unboxed = boxed;      // unboxing: Integer -> int, automatic

ArrayList<Integer> list = new ArrayList<>();
list.add(10);            // the int 10 is autoboxed into an Integer automatically

Java handles the conversion between a primitive and its wrapper automatically in most contexts (autoboxing and unboxing), which is why ArrayList<Integer> feels almost as easy to use as an int[] even though it stores objects.

ArrayList Methods

An ArrayList is a resizable collection from java.util — unlike an array, it can grow and shrink as the program runs.

import java.util.ArrayList;

ArrayList<String> names = new ArrayList<>();
names.add("Ana");          // adds to the end
names.add("Ben");
names.add(0, "Cy");      // inserts at index 0, shifting others right

System.out.println(names.get(1));   // "Ana" — access by index
names.set(1, "Amy");        // replaces the element at index 1
names.remove("Ben");        // removes the first match by value
System.out.println(names.size());   // current element count

ArrayList Traversals

ArrayLists can be traversed the same two ways as arrays — but removing elements while traversing forward is a classic bug source, because remaining elements shift down to fill the gap.

// standard for loop
for (int i = 0; i < names.size(); i++) {
    System.out.println(names.get(i));
}

// enhanced for loop
for (String n : names) {
    System.out.println(n);
}

// BUGGY: removing while traversing forward skips elements
for (int i = 0; i < names.size(); i++) {
    if (names.get(i).equals("Ben")) {
        names.remove(i);   // everything after shifts left, but i still moves forward
    }
}

// FIX: traverse backwards when removing
for (int i = names.size() - 1; i >= 0; i--) {
    if (names.get(i).equals("Ben")) {
        names.remove(i);
    }
}

Implementing ArrayList Algorithms

The same accumulator patterns (2.9, 4.5) work with ArrayLists — swap arr[i] for list.get(i) and arr.length for list.size().

ArrayList<Integer> nums = new ArrayList<>(List.of(4, 9, 2, 7));
int sum = 0;
for (int n : nums) {
    sum += n;
}

// building a NEW filtered list, rather than removing in place
ArrayList<Integer> evens = new ArrayList<>();
for (int n : nums) {
    if (n % 2 == 0) evens.add(n);
}

2D Array Creation and Access

A 2D array models a grid — rows and columns — as an array of arrays.

int[][] grid = new int[3][4];   // 3 rows, 4 columns, all 0
grid[1][2] = 7;             // row 1, column 2

int[][] literal = {
    {1, 2, 3},
    {4, 5, 6}
};   // 2 rows, 3 columns

System.out.println(literal.length);       // 2 — number of rows
System.out.println(literal[0].length);    // 3 — length of row 0

• Access always goes array[row][column] — row index first.
• .length on the whole array gives the number of rows; .length on one row (array[i].length) gives that row's width.
• Rows don't have to be the same length — this is called a jagged array — though most problems use uniform rectangular grids.

2D Array Traversals

Traversing a 2D array uses nested loops (2.11) — the outer loop walks rows, the inner loop walks columns within that row.

for (int row = 0; row < grid.length; row++) {
    for (int col = 0; col < grid[row].length; col++) {
        System.out.print(grid[row][col] + " ");
    }
    System.out.println();   // new line after each row
}

// enhanced for loop version — nested, since each "row" is itself an array
for (int[] r : grid) {
    for (int val : r) {
        System.out.print(val + " ");
    }
}

Implementing 2D Array Algorithms

2D array algorithms combine the nested-traversal pattern with accumulator logic — often tracked per row, per column, or across the whole grid.

int[][] grid = {{1,2,3},{4,5,6},{7,8,9}};

// sum of each row
for (int row = 0; row < grid.length; row++) {
    int rowSum = 0;
    for (int col = 0; col < grid[row].length; col++) {
        rowSum += grid[row][col];
    }
    System.out.println("Row " + row + " sum: " + rowSum);
}

// main diagonal (only defined for square grids)
int diagonalSum = 0;
for (int i = 0; i < grid.length; i++) {
    diagonalSum += grid[i][i];
}

Searching Algorithms

Two standard approaches for finding a value inside a collection:

// linear search — checks every element until found
public static int linearSearch(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;   // not found
}

// binary search — repeatedly halves the search range (array MUST be sorted)
public static int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Sorting Algorithms

Selection sort repeatedly finds the smallest remaining element and swaps it into its correct position.

public static void selectionSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[minIndex]) minIndex = j;
        }
        // swap the found minimum into position i
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

Each pass, the "sorted region" at the front grows by one element. With n elements, this takes roughly n passes, each scanning the shrinking remainder — giving O(n²) overall (2.12), same shape as a nested loop.

Recursion

A recursive method calls itself to solve a smaller version of the same problem. Every correct recursive method needs two parts:

• A base case — the simplest input, handled directly with no further recursive call. Without one, the recursion never stops.
• A recursive case — calls itself with an input that's closer to the base case than the current one.

public static int factorial(int n) {
    if (n == 0) return 1;             // base case
    return n * factorial(n - 1);   // recursive case
}
// factorial(4) → 4 * factorial(3) → 4 * (3 * factorial(2)) → ... → 4*3*2*1*1 = 24

Each call waits on the call stack for the call below it to return before it can finish its own multiplication — this is why recursion "unwinds" back up once it hits the base case.

Recursive Searching and Sorting

The searching and sorting ideas from 4.14–4.15 can be written recursively — each call handles one small piece, then recurses on the rest.

// recursive binary search
public static int binarySearch(int[] arr, int target, int lo, int hi) {
    if (lo > hi) return -1;                 // base case: range is empty, not found
    int mid = (lo + hi) / 2;
    if (arr[mid] == target) return mid;      // base case: found it
    else if (arr[mid] < target)
        return binarySearch(arr, target, mid + 1, hi);  // recurse right half
    else
        return binarySearch(arr, target, lo, mid - 1);  // recurse left half
}

Merge sort is a classic recursive sort: split the array in half, recursively sort each half, then merge the two sorted halves back together. Because it halves the problem each time (like binary search), it runs in O(n log n) — faster than selection sort's O(n²) on large inputs.