Why Do We Need Traversal?

In Topic 4.11, we learned how to create, access, and update individual elements in a 2D array.

For example:

String[][] groups = {
    {"Alice", "Bob", "Cara"},
    {"David", "Emma", "Frank"},
    {"Grace", "Henry", "Isabella"}
};

Accessing one specific element is easy:

System.out.println(groups[1][2]);

Output:

Frank

However, what if we wanted to print every student in every subgroup?

Instead of writing:

System.out.println(groups[0][0]);
System.out.println(groups[0][1]);
System.out.println(groups[0][2]);
System.out.println(groups[1][0]);
...

we use traversal.

Traversal means visiting each element in a data structure exactly once.

For 2D arrays, traversal is usually done with nested loops.


Understanding Nested Loops

A nested loop is a loop inside another loop.

Example:

Code Runner Challenge

Predict how many lines print and the first three pairs, then run it

View IPYNB Source
// CODE_RUNNER: Predict how many lines print and the first three pairs, then run it
public class NestedLoops {
    public static void main(String[] args) {
        for (int row = 0; row < 3; row++) {
            for (int col = 0; col < 2; col++) {
                System.out.println("(" + row + "," + col + ")");
            }
        }
    }
}
NestedLoops.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

The outer loop controls the row.

The inner loop controls the column.

This mirrors how a 2D array is organized.


Traversing a 2D Array

Consider the following array:

Code Runner Challenge

Predict the order the numbers print in, then run it to check

View IPYNB Source
// CODE_RUNNER: Predict the order the numbers print in, then run it to check
public class TraverseGrid {
    public static void main(String[] args) {
        int[][] numbers = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        // To visit every element: the outer loop picks the row, the inner loop walks its columns.
        for (int row = 0; row < numbers.length; row++) {
            for (int col = 0; col < numbers[row].length; col++) {
                System.out.println(numbers[row][col]);
            }
        }
    }
}
TraverseGrid.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Notice the use of:

numbers.length

This gives the number of rows.

And:

numbers[row].length

This gives the number of columns in that row.

Using .length makes the code work even if the dimensions change.


Visualizing Traversal

1 2 3
4 5 6
7 8 9

Traversal order:

1
2
3
4
5
6
7
8
9

The traversal moves across a row first, then moves down to the next row.

This is called row-major order, which is the order used most often in AP CSA.


Enhanced For Loops with 2D Arrays

Java also allows enhanced for loops.

for(int[] row : numbers) {
    for(int value : row) {
        System.out.println(value);
    }
}

The enhanced for loop automatically moves through each row and each value.

Advantages:

  • Shorter code
  • Easier to read

Disadvantages:

  • No access to row numbers
  • No access to column numbers

For AP CSA questions involving positions, traditional nested loops are usually preferred.


Common AP CSA Pattern: Printing a Grid

String[][] board = {
    {"X","O","X"},
    {"O","X","O"},
    {"X"," ","X"}
};

for(int row = 0; row < board.length; row++) {
    for(int col = 0; col < board[row].length; col++) {
        System.out.print(board[row][col] + " ");
    }
    System.out.println();
}

Output:

X O X
O X O
X   X

Notice that the outer loop controls rows and the inner loop controls columns.


Common AP CSA Pattern: Counting Elements

Suppose we want to count how many times the number 5 appears.

int count = 0;

for(int row = 0; row < numbers.length; row++) {
    for(int col = 0; col < numbers[row].length; col++) {
        if(numbers[row][col] == 5) {
            count++;
        }
    }
}

This is one of the most common AP CSA traversal patterns.


HACKS

Part 1: AP CSA Multiple Choice

5 questions. Use the tabs to move between them, and check an answer as many times as you need. Each check saves that answer, and your last saved answers are sent when you click Submit Code at the bottom of this page.

MCQ 4.12

Check each answer as many times as you need. Your last saved answers are the ones submitted.


Part 2: Code Hack

Use the exact 2D array of student groups that you created in Topic 4.11.

Example:

String[][] groups = {
    {"Alice", "Bob", "Cara"},
    {"David", "Emma", "Frank"},
    {"Grace", "Henry", "Isabella"}
};

Step 1

Identify the student located at:

Row 1, Column 1

Write a comment explaining who is located there.

Example:

Emma is located at row 1 column 1.

Step 2

Write the Java statement that would access that student.

Example:

System.out.println(groups[1][1]);

Step 3

Using a nested loop, print every student in your group.

for(int row = 0; row < groups.length; row++) {
    for(int col = 0; col < groups[row].length; col++) {
        System.out.println(groups[row][col]);
    }
}

Code Runner Challenge

Put your group in the array, say who is at row 1 column 1, then print everyone with a nested loop

View IPYNB Source
// CODE_RUNNER: Put your group in the array, say who is at row 1 column 1, then print everyone with a nested loop
public class GroupTraversal {
    public static void main(String[] args) {
        // Step 1: TODO replace these names with your group (one row per subgroup).
        String[][] groups = {
            {"Alice", "Bob", "Cara"},
            {"David", "Emma", "Frank"}
        };

        // Step 2: who is at row 1, column 1? TODO write your answer in this comment.
        System.out.println(groups[1][1]);

        // Step 3: print every student.
        for (int row = 0; row < groups.length; row++) {
            for (int col = 0; col < groups[row].length; col++) {
                System.out.println(groups[row][col]);
            }
        }
    }
}
GroupTraversal.main(null);
Lines: 1 Characters: 0
Output
Click "Run" in code control panel to see output ...

Reflection

  1. Why do we need nested loops for 2D arrays?
  2. What does the outer loop control?
  3. What does the inner loop control?
  4. Why is using .length better than hard-coding numbers like 3 or 4?

Submit Assignment

Choose what to hand in: click Add to submission on each runner you want graded (hacks, popcorn hacks), and save it. Leaving out practice runners does not lower your grade, but a required hack you leave out is graded as missing. Your selection is sent as a Gist for automatic review.

    Need to update a submission later? Open the submissions dashboard.