Data Collections

What this unit covers

The topics below follow the published CS A course framework for Unit 4. This unit is worth 30–40% of the exam, so budget your time against that rather than against how long the unit takes to teach.

Lessons in this unit

• 1D Arrays13 min · 3 objectivesCreate arrays with a literal or with `new`, and access elements by index · Use `.length` to find the number of elements · Recall the default values that `new` gives array elements
• ArrayList15 min · 3 objectivesCreate an `ArrayList` and use `add`, `get`, `size`, and `remove` · Explain how `remove(index)` shifts the remaining elements · Predict results of retrieving elements after modifying the list
• 2D Arrays14 min · 3 objectivesCreate a 2D array and access an element with `[row][col]` · Find the number of rows and columns from the array’s length fields · Trace element access in a rectangular grid
• Traversals, Searching & Sorting15 min · 3 objectivesUse an enhanced for-each loop to traverse and accumulate over an array · Trace a linear search for the maximum value · Distinguish reading elements (for-each) from needing indices (standard for)

Formulas in Unit 4

Every term in Unit 4

All 63 terms we publish for Data Collections, with definitions. Reading them through is the fastest way to find the ones you cannot define — then drill those in cram mode until you can produce them without the prompt.

Array

A fixed-size, ordered collection of values of one type. Its length is set at creation and can never change.

Declaring and creating an array

int[] a = new int[5]; creates five elements, all initialized to 0. String[] s = new String[5]; creates five nulls.

Array initializer list

int[] a = {3, 1, 4}; creates and fills in one statement. The length comes from the number of values.

array.length

A field, with no parentheses. Strings use length() and ArrayLists use size() — three collections, three different spellings, and the exam tests all of them.

Array indexing

Valid indices run from 0 to length − 1. Any other index throws ArrayIndexOutOfBoundsException at run time.

Traversing an array with an indexed for loop

for (int i = 0; i < a.length; i++). Use this whenever you need the index or need to modify elements.

Enhanced for loop

for (int x : a) visits each element in order. Simpler, but you get a copy of each element and no index.

Why an enhanced for loop cannot modify an array

The loop variable is a copy of the element, so assigning to it changes the copy. To modify the array you need an indexed loop.

Enhanced for loop with objects

The loop variable is a copy of the reference, so it points at the same object. You cannot replace an element, but you can call a mutator on it.

Array of objects

Each element is a reference, initially null. Creating the array does not create the objects — each must be assigned before use, or you get a NullPointerException.

ArrayList

A resizable ordered collection of objects. Grows and shrinks as elements are added and removed, unlike an array.

Declaring an ArrayList

ArrayList<String> list = new ArrayList<String>(); The type parameter must be a class, so use Integer and Double rather than int and double.

add(obj)

Appends to the end and returns true. The size increases by one.

add(index, obj)

Inserts at the given index and shifts everything from there right. Valid indices for this call run from 0 to size().

get(index)

Returns the element at the index without removing it. Out of range throws IndexOutOfBoundsException.

set(index, obj)

Replaces the element at the index and returns the old value. The size does not change.

remove(index)

Removes the element, shifts everything after it left, and returns the removed element. The size decreases by one.

size()

The number of elements currently in the ArrayList. With parentheses — unlike array.length.

The remove-while-looping bug

Removing an element shifts the rest left, so the next index is skipped. Either loop backward, or do not increment the counter when you remove.

Looping backward to remove safely

for (int i = list.size() − 1; i >= 0; i−−). Removals only shift elements you have already visited, so nothing is skipped.

Array vs ArrayList

Arrays are fixed-size, can hold primitives, and use .length and [i]. ArrayLists resize, hold only objects, and use size(), get() and set().

ArrayList of Integer and unboxing

list.get(0) returns an Integer, which unboxes to int automatically. If the element is null, that unboxing throws NullPointerException.

2D array

An array of arrays, declared int[][] grid = new int[3][4] — three rows of four columns each.

Row and column length

grid.length is the number of rows; grid[0].length is the number of columns in row 0. Reversing them is the standard 2D error.

Traversing a 2D array in row-major order

Outer loop over rows, inner loop over columns: for (int r...) for (int c...) grid[r][c]. This is the default order the exam assumes.

Column-major traversal

Outer loop over columns, inner over rows. Same elements, different order, and a question naming column-major wants that order in the output.

Enhanced for loop over a 2D array

for (int[] row : grid) for (int x : row). The outer variable is a whole row, which is itself an array.

2D array with unequal rows

Java allows rows of different lengths, so always use grid[r].length for the inner bound rather than grid[0].length.

Sequential search on an array

Loop from index 0, return the index when found, and return −1 after the loop if it was not. Returning 0 for "not found" is wrong — 0 is a valid index.

Binary search on a sorted array

Track low and high, compute mid, compare, and move low or high past mid. Loop while low <= high; using < skips the final single-element check.

Selection sort

Repeatedly find the smallest value in the unsorted portion and swap it into the next position. After pass k, the first k elements are in final sorted order.

Insertion sort

Take each element in turn and slide it left into its place among the already-sorted elements. After pass k, the first k + 1 elements are sorted relative to each other but not necessarily final.

Selection sort vs insertion sort after one pass

Selection sort puts one element in its permanent final position. Insertion sort orders a prefix that may all move later. Exam questions ask for the array state after a specific pass, and the two differ.

Merge sort

Divide the array in half, sort each half, then merge the sorted halves. Divide-and-conquer and recursive, and on the current exam you trace it rather than write it.

Merging two sorted halves

Compare the front elements of each half and take the smaller, repeatedly, until one half empties, then copy the rest. This is the step tracing questions test.

Why merge sort is faster on large arrays

It does about n log n comparisons, while selection and insertion sort do about n². For a thousand elements that is roughly ten thousand against a million.

Swapping two elements

A temporary variable is required: temp = a[i]; a[i] = a[j]; a[j] = temp. Assigning directly loses one of the values.

Standard algorithm: sum of a 2D array

Nested loops with an accumulator declared before both. Declaring it inside the outer loop resets it each row and returns only the last row's total.

Standard algorithm: row and column totals

A row total needs an accumulator reset at the start of each row. A column total needs the loops swapped so the column index is outer.

Standard algorithm: find max in a 2D array

Initialize to grid[0][0] rather than 0, then compare every element. Initializing to zero fails on an all-negative grid.

Standard algorithm: copy an array

Loop and assign element by element. `b = a;` copies the reference, so both names then refer to one array and changing either changes both.

Standard algorithm: build a filtered list

Create a new ArrayList, loop the source, and add only the elements that qualify. Safer than removing from the original while looping over it.

Standard algorithm: count elements meeting a condition

A counter before the loop, incremented inside the if, returned after. Works identically for arrays, ArrayLists and 2D arrays.

Standard algorithm: shift elements left

for (int i = 0; i < a.length − 1; i++) a[i] = a[i + 1]; then handle the last element. Going to a.length throws an exception on the final read.

ArrayList of objects

get(i) returns a reference to the object, so calling a mutator on it changes the object in the list. No set() call is needed for that.

Traversing to modify an ArrayList of objects

An enhanced for loop is fine when you are calling mutators, since the object is shared. It is not enough when you need to replace elements — that needs set() and an index.

Off-by-one in array bounds

i <= a.length throws an exception on the last pass; i < a.length − 1 silently skips the last element. Both compile, and only one of them tells you.

ArrayIndexOutOfBoundsException

Thrown at run time when an index is negative or at least the length. The message includes the offending index, which usually identifies the bug directly.

Choosing an array or an ArrayList

An array when the size is known and fixed, or when storing primitives efficiently. An ArrayList when elements are added or removed during execution.

Nested collection traversal cost

A loop inside a loop over the same n elements does about n² operations. Doubling the data roughly quadruples the work, which is the informal efficiency comparison the exam wants.

Tracing a sorting question

Write the array as a row of boxes and redraw it after each pass rather than each comparison. Questions ask for the state after a pass, and per-comparison tracing invites arithmetic slips.

Returning an array from a method

The return type is written int[] and the method returns the reference. The caller and the method then share one array.

Array parameter mutation

A method receiving an array can change its elements, and the caller sees those changes. Reassigning the parameter itself does not affect the caller.

Initializing an ArrayList with values

There is no initializer-list shorthand — create it empty and call add() for each element, usually in a loop.

Removing all matching elements

Loop backward and remove, or build a new list of keepers. A forward loop with removal skips the element after each removal.

Comparing objects in a collection

Use equals(), not ==. Two distinct objects with identical contents are never == to each other.

Null element in a collection

A collection can hold null. Calling a method on the retrieved element then throws NullPointerException, which is why traversals over object arrays often check for null first.

Array of Strings and .length confusion

names.length is the number of Strings; names[0].length() is the number of characters in the first one. Both appear in the same question deliberately.

2D array element assignment

grid[r][c] = value assigns one cell. grid[r] = someArray replaces an entire row with a different array reference.

Efficiency of insertion into an ArrayList

add(obj) appends cheaply. add(0, obj) shifts every existing element right, so repeating it in a loop is far more work than appending.

Total iterations over a 2D array

rows × columns for a rectangular grid. For a ragged one, sum each row's length rather than multiplying.

Building a String in a loop

Concatenate onto an accumulator initialized to the empty String "". Initializing it to null produces the text "null" at the front of the result.

Traversing part of a collection

Adjust the bounds rather than the body: start at 1 to skip the first, stop at length − 1 to skip the last. Guarding inside the loop with an if works but is harder to read and easier to get wrong.

What examiners penalize here

• An index runs from 0 to `length - 1`. To loop over every element, use `for (int i = 0; i < arr.length; i++)` — note the strict `<`, which stops correctly at the last valid index.
• When removing elements in a loop, remember each `remove(i)` shifts later elements left. Iterating forward with a normal index can skip elements — a very common FRQ trap.
• To traverse a full grid, use `for (int r = 0; r < m.length; r++)` outside and `for (int c = 0; c < m[0].length; c++)` inside. The outer loop walks rows, the inner walks columns.
• Seed a max/min search with `a[0]` and start the loop at index 1. Seeding with 0 can be wrong for arrays of all-negative numbers, and forgetting to update `max` leaves it stuck at the first value.

Practice CS A

Our practice bank is drawn from across the whole course rather than filtered to one unit, which is closer to how the exam asks anyway — it will not tell you which unit a question is testing.

Questions about this unit

All 4 units of AP Computer Science A

1. Unit 1 · Using Objects and Methods
2. Unit 2 · Selection and Iteration
3. Unit 3 · Class Creation
4. Unit 4 · Data Collections