Array Traversals - AP Computer Science A

SECTION 1

Historical Context & Motivation

The concept of iterating over a sequence of stored values is as old as programming itself. Before high-level languages existed, early programmers manipulated memory addresses directly, stepping through contiguous blocks of data one word at a time on machines like the ENIAC and EDVAC. The need to systematically visit every element in a collection — what we now call an array traversal — drove the invention of loop constructs, index registers, and eventually the elegant for loop syntax we use in Java today. Understanding this history illuminates why arrays and their traversals remain central to computer science: they reflect the physical reality of how data is laid out in memory.

1945 • Stored-Program Concept

John von Neumann's draft report on the EDVAC describes storing data in sequential memory cells, establishing the conceptual basis for arrays as contiguous blocks of addressable memory.

1957 • FORTRAN Introduces Indexed Arrays

IBM's FORTRAN language provides the first high-level array syntax with DO loops for traversal, liberating programmers from manual address arithmetic and making array processing accessible.

1972 • C Formalizes Pointer-Array Duality

Dennis Ritchie's C language treats array names as pointers to their first element, making traversal via pointer arithmetic and index-based loops interchangeable — a design that deeply influenced Java.

1995 • Java's Array Model

Java introduces bounds-checked arrays as objects with a built-in length field, eliminating buffer overflow vulnerabilities while preserving O(1) indexed access and O(n) traversal patterns.

2004 • Enhanced for Loop (for-each)

Java 5 adds the enhanced for loop, providing a cleaner syntax for read-only traversals and signaling that iteration is so common it deserves its own language construct.

The core question that array traversals answer is deceptively simple: how do you reliably process every element in a collection exactly once? This question becomes nuanced when you consider partial traversals (stopping early when a condition is met), reverse traversals, simultaneous modification during traversal, and the performance implications of different access patterns. Mastering these patterns is essential not only for the AP Computer Science A exam but for virtually every software system you will ever build.

SECTION 2

Core Principles & Definitions

An array is a fixed-size, ordered collection of elements, all of the same type, stored in contiguous memory. Each element is accessed by its index — an integer starting at 0 and extending to array.length - 1. A traversal is the process of visiting elements in a sequence, typically to inspect, transform, accumulate, or filter them. The following principles govern how traversals work in Java and appear on the AP exam.

Zero-Based Indexing

Java arrays begin at index 0. The last valid index is length - 1. Accessing an index outside this range throws an ArrayIndexOutOfBoundsException at runtime.

Standard for Loop

The classic for (int i = 0; i < arr.length; i++) pattern gives full control over the index variable, enabling forward, reverse, and partial traversals as well as element modification.

Enhanced for Loop (for-each)

The syntax for (int val : arr) iterates from index 0 to the end. It is read-only with respect to the array itself — assigning to the loop variable does not modify the original array element.

Traversal Patterns

Common patterns include accumulation (summing, counting), searching (finding a value or index), filtering (building a new collection), and transformation (modifying elements in place). Each pattern builds on the basic traversal skeleton.

Off-by-One Errors

The most frequent traversal bug. Using <= instead of < in the loop condition, or starting at index 1 instead of 0, causes missed elements or exceptions. Careful boundary reasoning prevents these errors.

✦

KEY TAKEAWAY

Think of an array traversal like a librarian conducting inventory by walking down a single shelf of books. The standard for loop is like having the shelf positions numbered — you can start anywhere, skip sections, or walk backwards. The enhanced for loop is like pulling each book off the shelf into your hands one at a time — simpler, but you cannot rearrange the shelf while doing it. Choose the right tool based on whether you need the position number or just the book.

SECTION 3

Visual Explanation

The following diagram illustrates how a standard for loop traverses a five-element integer array. Each iteration advances the index variable i by one, accesses the element at that position, and processes it. The highlighted cell shows the element currently being visited, while the accumulator variable tracks a running sum — one of the most common traversal patterns.

The diagram shows a five-element array with indices 0 through 4. Each row in the iteration trace shows the current value of i, the element accessed, and the updated accumulator. When i reaches 5, the condition i < arr.length evaluates to false and the loop terminates.

Notice how the loop variable i serves dual purposes: it controls the number of iterations and it provides the index to access each element. The condition i < arr.length (using strict less-than, not less-than-or-equal) ensures we never attempt to access index 5 in a five-element array. This boundary condition is the single most important detail in any array traversal. The iteration trace also reveals that the loop body executes exactly arr.length times — a property that holds regardless of the array's contents, making it a complete traversal.

SECTION 4

How Traversals Work — Loop Mechanics

Understanding the mechanical execution of a loop is essential for predicting output, debugging off-by-one errors, and writing correct traversals under exam pressure. Every for loop has three components — initialization, condition, and update — that together determine exactly which indices are visited.

STANDARD FOR LOOP ANATOMY

for (init; condition; update) { body }

init executes once before the first iteration. condition is evaluated before each iteration; if false, the loop terminates. update executes after each iteration completes.

FORWARD TRAVERSAL (ALL ELEMENTS)

for (int i = 0; i < arr.length; i++)

Visits indices 0, 1, 2, …, n−1 where n = arr.length. Total iterations: n. This is the canonical complete forward traversal.

REVERSE TRAVERSAL

for (int i = arr.length - 1; i >= 0; i--)

Visits indices n−1, n−2, …, 1, 0. Useful when removing elements or processing from end to start. Note the >= condition, which includes index 0.

ENHANCED FOR LOOP (FOR-EACH)

for (Type element : arr)

Implicitly iterates from index 0 to n−1. The variable element holds a copy of each array value. You cannot modify the array through this variable, and you have no access to the current index.

⚠

AP Exam Alert

The AP Computer Science A exam frequently tests whether students can identify the difference between modifying arr[i] inside a standard for loop (which changes the array) and assigning to the loop variable in an enhanced for loop (which does not change the array). This distinction appears in multiple-choice questions nearly every year.

A while loop can also traverse an array when you manage the index variable manually. The pattern int i = 0; while (i < arr.length) { /* body */ i++; } is functionally equivalent to the standard for loop but requires the programmer to remember the update step — forgetting it results in an infinite loop. While loops are especially useful for early termination traversals where you stop as soon as a target element is found.

SECTION 5

Common Traversal Patterns

While the loop skeleton remains consistent, the body of a traversal changes dramatically depending on the task. The AP exam expects you to recognize and implement several canonical traversal patterns. The diagram below classifies these patterns, and the table that follows provides code templates for each.

The tree diagram classifies traversal patterns into three families — accumulate, search, and transform/filter — with code templates and loop-choice guidance. The decision matrix at the bottom helps you select the appropriate loop construct based on your task requirements.

Pattern	Loop Type	Key Detail	Example Use
Sum / Count	Either	Initialize accumulator before loop	`sum += arr[i]`
Min / Max	Either	Initialize to first element, start loop at index 1	`if (arr[i] > max) max = arr[i]`
Linear Search	Standard for	Return index when found; return −1 after loop	`if (arr[i] == key) return i`
All / Any	Either	"All" starts true, set false on counterexample; "Any" starts false, set true on match	`if (arr[i] < 0) allPositive = false`
Shift / Remove	Standard for	Traverse backward to avoid skipping elements during removal	`arr[i] = arr[i + 1]`

Canonical traversal patterns tested on the AP Computer Science A exam

SECTION 6

Worked Example

Consider the following problem: given an array of integers, write a method that returns the number of elements greater than the average of all elements. This problem requires two traversals — one to compute the average, and a second to count elements exceeding it.

Count Elements Above Average

1
Step 1 — Understand the Input

We are given int[] data = {4, 8, 2, 10, 6}. We need to find how many elements are strictly greater than the average value.

Array has 5 elements: {4, 8, 2, 10, 6}
2
Step 2 — First Traversal: Compute the Sum

Use an enhanced for loop to accumulate the sum, since we only need the values, not the indices: int sum = 0; for (int val : data) { sum += val; }. After the loop, sum = 4 + 8 + 2 + 10 + 6 = 30.

sum = 30
3
Step 3 — Compute the Average

Divide sum by length: double avg = (double) sum / data.length. The cast to double ensures floating-point division. Without the cast, integer division would yield 6 instead of 6.0 — in this case numerically the same, but in general this distinction matters.

avg = 30.0 / 5 = 6.0
4
Step 4 — Second Traversal: Count Elements Above Average

Use another enhanced for loop: int count = 0; for (int val : data) { if (val > avg) count++; }. We check each element: 4 > 6.0? No. 8 > 6.0? Yes. 2 > 6.0? No. 10 > 6.0? Yes. 6 > 6.0? No (strict inequality excludes 6.0 itself).

count = 2
5
Step 5 — Return the Result

The method returns 2. The complete method signature would be public static int countAboveAverage(int[] data). Note that this solution performs two separate traversals, each O(n), giving an overall time complexity of O(n) — not O(n²), because the traversals are sequential, not nested.

Return value: 2 (elements 8 and 10 exceed the average of 6.0)

SECTION 7

Loop Constructs — Strengths & Limitations

Java provides multiple loop constructs for array traversal, each with distinct trade-offs. The AP exam expects you to select the appropriate construct for a given task and to recognize when a particular loop type is unsuitable. The following comparison table summarizes the capabilities and constraints of each option.

Feature	Standard for	Enhanced for (for-each)	while
Index access	Yes — full control over i	No — index not exposed	Yes — manual management
Modify array elements	Yes — via arr[i] = ...	No — loop variable is a copy	Yes — via arr[i] = ...
Reverse traversal	Yes — decrement i	No — always forward	Yes — decrement index
Skip elements	Yes — i += 2, etc.	No — visits all elements	Yes — custom increment
Off-by-one risk	Moderate — boundary conditions	Low — bounds handled automatically	High — easy to forget update
Readability	Good — familiar to all Java developers	Excellent — intent is clear	Fair — more boilerplate

Comparison of Java loop constructs for array traversal

💡

RULE OF THUMB

Use the enhanced for loop as your default for read-only complete traversals — it eliminates an entire class of bugs. Switch to a standard for loop whenever you need the index, must modify the array, or require non-sequential access. Think of it like choosing between an automatic and manual transmission: the automatic is simpler for everyday driving, but the manual gives you the control needed for advanced maneuvers.

SECTION 8

Connection to ArrayList and Advanced Iteration

Array traversal patterns translate directly to ArrayList traversals, which the AP exam tests equally. The key difference is syntactic: instead of arr[i] you use list.get(i), and instead of arr.length you use list.size(). However, ArrayLists introduce an important subtlety: when you remove an element during traversal using list.remove(i), subsequent elements shift left, which can cause you to skip an element if you increment the index. This is why backward traversal is preferred for removal — a concept that appears frequently in free-response questions.

Operation	Array Syntax	ArrayList Syntax
Get length / size	`arr.length`	`list.size()`
Access element at index i	`arr[i]`	`list.get(i)`
Set element at index i	`arr[i] = val`	`list.set(i, val)`
For-each traversal	`for (int x : arr)`	`for (Integer x : list)`
Remove during traversal	Shift manually (arrays are fixed-size)	`list.remove(i); i--`

Array vs. ArrayList traversal syntax comparison

Beyond the AP syllabus, array traversals form the basis for more sophisticated iteration abstractions. Java's Iterator interface and the Stream API both generalize the traversal concept. In data structures courses, you will encounter traversals of linked lists, trees, and graphs — each requiring different strategies (depth-first, breadth-first, in-order) but rooted in the same fundamental idea: visit elements systematically and process them according to a pattern. Mastering array traversals now provides the conceptual scaffolding for all of these advanced techniques.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Consider the following code segment:

int[] arr = {3, 7, 1, 9, 5};
for (int x : arr)
{
    x = x + 1;
}
System.out.println(arr[2]);

What is printed as a result of executing the code segment?

A. 1
B. 2
C. 7
D. An ArrayIndexOutOfBoundsException is thrown

Show answer (A)

The correct answer is A (1). The enhanced for loop assigns a copy of each array element to the variable x. The statement x = x + 1 modifies only the local copy, not the array itself. After the loop completes, arr is unchanged, so arr[2] still holds 1. Choice B (2) incorrectly assumes the array was modified. Choice C (7) confuses index 2 with index 1. Choice D is wrong because index 2 is valid for a five-element array (valid indices are 0–4).

Question 2: BASIC CALCULATION

Consider the following method:

public static int mystery(int[] a)
{
    int result = a[0];
    for (int i = 1; i < a.length; i++)
    {
        if (a[i] < result)
            result = a[i];
    }
    return result;
}

What value is returned by the call mystery(new int[]{5, 3, 8, 1, 4})?

A. 8
B. 5
C. 1
D. 3

Show answer (C)

The correct answer is C (1). This method finds the minimum value in the array. It initializes result to the first element (5), then traverses from index 1 onward. At index 1, 3 < 5 so result becomes 3. At index 2, 8 < 3 is false. At index 3, 1 < 3 so result becomes 1. At index 4, 4 < 1 is false. The final value is 1. Choice A (8) would be the maximum, not the minimum. Choice B (5) would result from not entering the loop or a wrong initial assumption. Choice D (3) represents the state after processing only the first two elements.

Question 3: INTERMEDIATE

Consider the following code segment:

int[] arr = {1, 2, 3, 4, 5, 6};
int count = 0;
for (int i = 0; i < arr.length; i += 2)
{
    if (arr[i] % 2 != 0)
        count++;
}
System.out.println(count);

What is printed as a result of executing the code segment?

A. 2
B. 3
C. 6
D. 0

Show answer (B)

The correct answer is B (3). The loop uses a step of 2 (i += 2), so it visits indices 0, 2, and 4 only. The elements at those indices are 1, 3, and 5 — all odd. The condition arr[i] % 2 != 0 is true for all three, so count reaches 3. Choice A (2) likely results from miscounting which indices are visited. Choice C (6) would result from visiting all 6 elements and counting all as odd, which is incorrect. Choice D (0) would result from confusing the condition to check for even numbers.

Question 4: APPLIED

5 pts

A teacher stores student scores in an integer array. Write a method public static double[] normalize(int[] scores) that returns a new double array where each element is the original score divided by the maximum score in the array. For example, if scores = {80, 100, 60, 90}, the maximum is 100, and the returned array is {0.8, 1.0, 0.6, 0.9}. You may assume the array has at least one element and all scores are positive.

Show answer

Rubric (5 points): Point 1 — Find maximum: Initializes a variable to scores[0] (or Integer.MIN_VALUE) and traverses the array to find the maximum value using a correct comparison. Point 2 — Create result array: Declares and instantiates a new double[] of the correct length (scores.length). Point 3 — Normalization traversal: Correctly iterates through all indices and computes each normalized value as (double) scores[i] / max, ensuring floating-point division (not integer division). Point 4 — Assigns to result array: Stores each computed value in the corresponding index of the result array. Point 5 — Returns result: Returns the result array. Sample solution:

public static double[] normalize(int[] scores)
{
    int max = scores[0];
    for (int i = 1; i < scores.length; i++)
    {
        if (scores[i] > max)
            max = scores[i];
    }
    double[] result = new double[scores.length];
    for (int i = 0; i < scores.length; i++)
    {
        result[i] = (double) scores[i] / max;
    }
    return result;
}

Question 5: CRITICAL THINKING

3 pts

A student writes the following method to remove all negative values from an ArrayList of integers:

public static void removeNegatives(ArrayList<Integer> list)
{
    for (int i = 0; i < list.size(); i++)
    {
        if (list.get(i) < 0)
            list.remove(i);
    }
}

(a) Explain why this method may fail to remove all negative values for certain inputs. Give a specific example ArrayList where the bug manifests. (b) Fix the method. You may rewrite it entirely or make minimal changes to the existing code.

Show answer

Rubric (3 points): Point 1 — Identifies the bug: When an element is removed at index i, all subsequent elements shift left by one. The loop then increments i, which causes it to skip the element that moved into position i. For example, with the list [-1, -2, 3], when i=0, -1 is removed and the list becomes [-2, 3]. Then i increments to 1, skipping -2 entirely. The method returns [-2, 3] instead of [3]. Point 2 — Provides a concrete failing example: Any ArrayList with two or more consecutive negative values demonstrates the bug, such as [-1, -2, 3] or [-3, -5, -7]. Point 3 — Correct fix: Either (a) traverse backward: for (int i = list.size() - 1; i >= 0; i--), which avoids the shifting problem because removed elements are always behind the current index; or (b) add i-- inside the if-block after removal to counteract the upcoming i++, keeping the index at the correct position; or (c) use a while loop that only increments i when no removal occurs.

SUMMARY

Summary

An array traversal is the systematic process of visiting elements in an array, typically using a standard for loop (for full index control and modification) or an enhanced for loop (for clean read-only access). Java arrays use zero-based indexing with valid indices from 0 to length − 1, and the loop condition i < arr.length (strict less-than) prevents ArrayIndexOutOfBoundsException. The most common traversal patterns are accumulation (sum, count, min/max), searching (linear search, contains), and transformation (modify in place or build a new array).

Key pitfalls include off-by-one errors (using <= instead of <), mistakenly believing the enhanced for loop modifies the array, and skipping elements when removing during a forward traversal of an ArrayList. These traversal skills transfer directly to ArrayList processing and form the foundation for more advanced iteration patterns encountered in later courses.