B2.2.2 · Data structures
1D and 2D arrays
By the end you can
Index, traverse, search, and update 1D arrays and 2D matrices using nested row-major loops.
An is a contiguous, indexed collection of elements of the same data type. Because elements occupy consecutive memory addresses, any element can be read or written in constant time ($O(1)$) using its numerical index.
One-dimensional (1D) arrays#
A 1D array represents a linear list. In 0-based indexing:
// Java declaration int[] scores = new int[5]; // Indices 0 to 4 scores[0] = 85; # Python list equivalent scores = [85, 92, 78, 64, 99] firstScore = scores[0]
Traversing a 1D array involves a single loop iterating from index 0 up to length - 1. Linear algorithms (calculating the sum, finding the maximum, or linear search) run in linear time ($O(n)$).
Two-dimensional (2D) arrays and matrices#
A 2D array models tables, grids, board games, and mathematical matrices. It is essentially an “array of arrays” where elements are referenced by two indices: [row][column].
To process every cell in a 2D grid, programmers use nested loops:
// Nested traversal in pseudocode
total = 0
loop R from 0 to NUM_ROWS - 1
loop C from 0 to NUM_COLS - 1
total = total + grid[R][C]
end loop
end loop
output totalIn row-major order, the outer loop iterates through rows and the inner loop traverses columns. This matches how RAM caches sequential memory blocks, making row-major traversal substantially faster in compiled languages.
Check yourself
1D and 2D arrays
Quick questions, made fresh every time and marked here. Do a few until they feel easy.
Exam practice
Paper 1-style questions
3 questions · 8 marks
Write your answer as you would in the exam, then show the mark points and tick each one your answer made. These are our own questions in the style of the exam, not past-paper questions.
1.A 2D array grid of size 3 rows by 4 columns is declared. State the index expression used to access the element in the second row and fourth column using 0-based indexing.
[2]State: Give a short answer, no explanation needed.
2.Construct nested loops in pseudocode to calculate and print the sum of all elements in a 2D integer array matrix with R rows and C columns.
[4]Construct: Draw or write it out (a table, a diagram, a program).
3.Explain why traversing a 2D array row by row (row-major order) is typically faster than column by column on modern processors.
[2]Explain: Give reasons: say what happens AND why, or how one thing causes another.
In a nutshell
- A 1D array is a linear list of elements of the same type stored consecutively in RAM with O(1) direct access.
- A 2D array models tables, grids, and matrices using two indices: [row][column].
- Nested loops are required to traverse 2D arrays, with the outer loop iterating rows and the inner loop iterating columns.
- Row-major order traverses elements along consecutive row addresses, maximizing CPU cache locality.