FundamentalsFundamentals
Matrix Layout & Traversal Order
A rectangular grid of values indexed by (row, column), stored as an array of rows or one flattened row-major array.
11
12
13
14
21
22
23
24
31
32
33
34
Linear memory — 3×4 = 12 slots, one row after another
0:111:122:133:144:215:226:237:248:319:3210:3311:34
1/29This 3×4 matrix looks two-dimensional on the page, but memory is one-dimensional: the 3 rows are stored end to end in a single run of 12 slots, row 0 first. The grid is a way of reading the run, not a shape the machine knows about.
Cell being accessed nowPrevious access (the jump starts here)Already visited in this traversal
PseudocodeLearn Matrix (2D Array) →
1a rows × cols matrix is ONE flat run of rows*cols slots2flat = r * cols + c # skip r whole rows, then c cells3row-major traversal:4 for r in 0 .. rows-1:5 for c in 0 .. cols-1: visit a[r][c] # next flat = +16column-major traversal:7 for c in 0 .. cols-1:8 for r in 0 .. rows-1: visit a[r][c] # next flat = +colsVariables
rows3
cols4
slots12
layoutrow-major
Complexity
access O(1)
search O(m·n)
insert O(m·n)
delete O(m·n)
Speed