Arrays and their storage representation
Arrays: definitions, index bounds, base address, element size, row-major/column-major order, stride and offset, address-calculation formulas for 1D/2D/kD arrays, static vs dynamic arrays, alignment, and exam-style derivations and programs.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Arrays are the simplest and most efficient way to store a fixed-size sequence of same-type data in contiguous memory, enabling O(1) random access. Engineers use arrays in embedded systems (sensor buffers), graphics (images as 2D arrays), compilers (symbol tables), and OS kernels (page tables) where predictable memory layout and fast indexing are critical.
Key ideas
- A dimension is the count of indices needed to select an element: a 1D array needs one index; a 2D array needs two; a kD (k-dimensional) array needs k.
- The lower bound (Lᵣ) and upper bound (Uᵣ) of the r-th dimension are the smallest and largest valid indices along that dimension. Many languages use Lᵣ = 0 (C, C++), some use Lᵣ = 1 (MATLAB), and some allow arbitrary bounds (Fortran, Pascal).
- The size along dimension r is Nᵣ = Uᵣ − Lᵣ + 1.
- The base address (base) is the address in memory where the first element (by storage order) is stored.
- The element size (w) is the number of bytes per element (e.g., 4 bytes for a 32-bit int). All elements in an array have same w.
- The address of an element is computed as base plus an offset in bytes: address = base + offset.
- The stride along a dimension is the number of elements you skip in memory when you increase that dimension’s index by one, keeping all higher-priority indices constant. Multiplying stride by element size gives the byte stride.
- Row-major order stores the last dimension contiguously; for 2D, entire rows are contiguous (e.g., C and C++ true multidimensional arrays).
- Column-major order stores the first dimension contiguously; for 2D, entire columns are contiguous (Fortran, MATLAB).
- Static array: size fixed at compile time; dynamic array: size decided at run time (allocated on heap), may also support resizing (e.g., Python list, C++ vector) by reallocation and copying.
- Memory alignment means addresses are multiples of some unit (e.g., 4 or 8 bytes) for speed; compilers may insert padding to align base.
- Contiguous storage representation means consecutive elements occupy successive memory addresses without gaps (aside from possible base alignment at the start).
Exact statements and derivations students must know:
- Exact definition (address law) for 1D array in contiguous memory
- Statement: Consider a 1D array A with lower bound L and upper bound U, element size w bytes, and base address base = addr(A[L]). For any index i with L ≤ i ≤ U, the address of A[i] is: address(A[i]) = base + (i − L)·w.
- Assumptions: contiguous elements, fixed element size, no padding between elements, valid index range.
- Derivation: By definition, A[L] is at base. Moving from A[i] to A[i+1] advances by one element = w bytes. From L to i is (i − L) steps, so offset = (i − L)·w.
- Exact definition (address law) for 2D array in row-major order
- Statement: For a 2D array A with bounds L₁..U₁ along rows, L₂..U₂ along columns, element size w, base = addr(A[L₁][L₂]), and sizes N₁ = U₁ − L₁ + 1, N₂ = U₂ − L₂ + 1, the address in row-major order is: address(A[i][j]) = base + [ (i − L₁)·N₂ + (j − L₂) ]·w.
- Assumptions: contiguous row-major layout, indices within bounds, fixed w.
- Derivation: Each completed row has N₂ elements. Number of elements before row i: (i − L₁)·N₂. Within row i, number of elements before column j: (j − L₂). Sum, then multiply by w to convert to bytes.
- Exact definition (address law) for 2D array in column-major order
- Statement: address(A[i][j]) = base + [ (j − L₂)·N₁ + (i − L₁) ]·w.
- Derivation mirrors row-major; now columns are contiguous, so full columns (N₁ each) accumulate first.
- General kD array address law in row-major order
- Statement: For a kD array with bounds Lᵣ..Uᵣ, sizes Nᵣ, element size w, base = addr(A[L₁][L₂]…[L_k]): address(A[i₁][i₂]…[i_k]) = base + [ Σ_{r=1 to k} (i_r − L_r)·S_r ]·w, where S_k = 1 and S_r = Π_{t=r+1 to k} N_t for r = 1..k−1. S_r are the element strides.
- Assumptions: row-major order, contiguous storage, indices within bounds.
- Derivation: Treat the multidimensional index as a mixed-radix number with radices N₁, N₂, …, N_k. The linear index equals Σ (i_r − L_r) multiplied by stride S_r.
- General kD array address law in column-major order
- Statement: address(A[i₁]…[i_k]) = base + [ Σ_{r=1 to k} (i_r − L_r)·S'_r ]·w, where S'_1 = 1 and S'r = Π{t=1 to r−1} N_t for r = 2..k.
- Assumptions and derivation: analogous to row-major, but strides accumulate from the first dimension outward.
- Access time and complexity
- Statement: Under the Random Access Machine (RAM) model, accessing any element of a fixed-size array by index is O(1) time, because address computation uses a constant number of arithmetic operations independent of the array size.
- Assumptions: indexes are valid, element size and base address known, the arithmetic is constant-time at the machine level.
What to draw and how to label (exam-diagram descriptions):
- 1D array in memory: Draw a horizontal row of equal-sized boxes labeled A[L], A[L+1], …, A[U]. Above the leftmost box write “base = addr(A[L])”. Mark width of each box as “w bytes”. Draw an address scale beneath: base, base + w, base + 2w, …
- 2D row-major layout: Draw a grid with rows i = L₁..U₁ and columns j = L₂..U₂. Then redraw as a single horizontal strip showing row 0 (or L₁) laid out first (A[L₁][L₂] to A[L₁][U₂]), then row 1, etc. Label N₂ as row length and show the offset formula: offset elements = (i − L₁)·N₂ + (j − L₂).
- 2D column-major layout: As above but strip columns: first column j = L₂ from i = L₁..U₁, then next column. Label offset = (j − L₂)·N₁ + (i − L₁).
- kD strides: Show a cube (3D) with axes i₁, i₂, i₃. Annotate S₁ = N₂·N₃, S₂ = N₃, S₃ = 1. Then show flattening into a line with these strides.
Language-specific notes (kept short; do not re-teach other topics):
- C/C++: row-major for multi-dimensional arrays; true multidimensional arrays have contiguous rows; but “array of pointers to rows” is not contiguous across rows. sizeof gives w; pointer arithmetic scaled by element size.
- Fortran/MATLAB: column-major.
- Python: list is a dynamic array of references (not contiguous elements of same type). The array module (array.array) stores contiguous primitive values. NumPy arrays (outside standard library) are contiguous by default and can have strides.
- Java: multi-dimensional arrays are arrays of arrays (rows may be separate blocks); primitive single arrays are contiguous.
Memory alignment and padding:
- Compilers align the base of an array so addr(A) is a multiple of element alignment (e.g., 4 or 8). Elements within a homogeneous array usually have no internal padding; padding appears between different fields in a struct, not between elements, except for vectorized types on some ABIs.
Static vs dynamic arrays:
- Static: size known at compile time (e.g., int a[10]; in C when size is a constant). Allocated in global/static area or stack (for auto arrays); lifetime tied to scope or program. Note: C (C99) also defines variable length arrays (VLAs) whose sizes are decided at run time but typically have automatic storage duration; they are contiguous like static arrays, optional in C11, and not supported in C++.
- Dynamic: size known at run time (e.g., malloc/new; Python list growth strategy). May reallocate to a new larger contiguous block when growing; this preserves amortized O(1) append (topic “Algorithm analysis” explains amortized analysis).
Contiguous vs jagged:
- Contiguous multi-dimensional array: one block with address laws above.
- Jagged array: an array of pointers to arrays; each row can be different length; not one single contiguous block; address laws above do not apply across rows.
Cache locality (brief intuition):
- Because of contiguity, iterating in the storage order (rows for row-major, columns for column-major) benefits CPU caches and improves performance.
Formulas
where base = addr(A[L]) in bytes, i is index with L ≤ i ≤ U, L lower bound, w element size in bytes; applies to 1D contiguous arrays.
address(A[i][j]) = base + [ (i − L₁)·N₂ + (j − L₂) ]·wbase = addr(A[L₁][L₂]) bytes; N₂ = U₂ − L₂ + 1; row-major 2D arrays.address(A[i][j]) = base + [ (j − L₂)·N₁ + (i − L₁) ]·wbase as above; N₁ = U₁ − L₁ + 1; column-major 2D arrays.S_k = 1; S_r = Π_{t=r+1 to k} N_tS_r are strides (in elements) for row-major kD arrays; N_t sizes per dimension (unit: elements).address(A[i₁]…[i_k]) = base + [ Σ_{r=1 to k} (i_r − L_r)·S_r ]·wbase bytes; w bytes; row-major kD arrays.S'_1 = 1; S'_r = Π_{t=1 to r−1} N_tstrides in elements for column-major.address(A[i₁]…[i_k]) = base + [ Σ_{r=1 to k} (i_r − L_r)·S'_r ]·wcolumn-major kD arrays.N_r = U_r − L_r + 1number of elements along dimension r (unit: elements).total_elements = Π_{r=1 to k} N_rtotal element count (unit: elements) for a kD array.total_bytes = total_elements · wmemory occupied by a contiguous array (unit: bytes).
Syntax to remember (C-like pseudocode):
int a[n]; // 1D static arrayint a[m][n]; // 2D row-major arrayint (*p)[n] = a; // pointer to row of n intsint **b; // jagged when rows allocated separatelyaddr = base + offset_in_elements * w; // address computation
Worked examples
Example 1 — Numerical derivation and calculation (2D row-major address) Given: A 2D integer array A with bounds: rows i from 1 to 4, columns j from 0 to 5. Each int is w = 4 bytes. Base address base = 1000 bytes (addr(A[1][0]) = 1000). Find the address of A[3][2] in row-major order.
Steps:
- Compute sizes: N₁ = U₁ − L₁ + 1 = 4 − 1 + 1 = 4 elements; N₂ = U₂ − L₂ + 1 = 5 − 0 + 1 = 6 elements.
- Use formula:
address(A[i][j]) = base + [ (i − L₁)·N₂ + (j − L₂) ]·w. - Substitute: i = 3, L₁ = 1 → (3 − 1)·N₂ = 2·6 = 12 elements. j = 2, L₂ = 0 → (2 − 0) = 2 elements. Total offset in elements = 12 + 2 = 14 elements.
- Convert to bytes: offset_bytes = 14 · 4 bytes = 56 bytes.
- Address: 1000 bytes + 56 bytes = 1056 bytes.
Final answer: addr(A[3][2]) = 1056 bytes.
Example 2 — Python program: compute linear address for both orders This program computes the byte address of A[i][j] given array metadata and prints both row-major and column-major addresses.
Python code:
# Program: address_2d.py
# Computes byte addresses for 2D arrays in row-major and column-major orders.
def address_row_major(base, L1, U1, L2, U2, w, i, j):
N1 = U1 - L1 + 1
N2 = U2 - L2 + 1
assert L1 <= i <= U1 and L2 <= j <= U2, "Index out of bounds"
offset_elems = (i - L1) * N2 + (j - L2)
return base + offset_elems * w
def address_col_major(base, L1, U1, L2, U2, w, i, j):
N1 = U1 - L1 + 1
N2 = U2 - L2 + 1
assert L1 <= i <= U1 and L2 <= j <= U2, "Index out of bounds"
offset_elems = (j - L2) * N1 + (i - L1)
return base + offset_elems * w
if __name__ == "__main__":
# Sample input (hard-coded for exam clarity):
base = 1000
L1, U1 = 1, 4
L2, U2 = 0, 5
w = 4
i, j = 3, 2
a_row = address_row_major(base, L1, U1, L2, U2, w, i, j)
a_col = address_col_major(base, L1, U1, L2, U2, w, i, j)
print(a_row)
print(a_col)
Sample input: (none; values are in the program)
Exact output:
1056
1040
Explanation: Row-major and column-major generally yield different addresses for the same (i,j) because they accumulate completed rows vs completed columns, respectively. With the given parameters, row-major gives 1056 while column-major gives 1040. They coincide only in special cases (e.g., when (i − L1)·(N2 − 1) = (j − L2)·(N1 − 1), or for degenerate 1×N or N×1 arrays), but in general the two orders produce different addresses and traversal sequences.
Example 3 — Python program: simulate 2D row-major storage from a 1D block This program stores a 2D matrix in a flat 1D list to mimic contiguous memory, then indexes using the row-major address law. It also shows the difference in traversal orders (row-major vs column-major) affecting the sequence of addresses/indices.
Python code:
# Program: flat_2d_row_major.py
# Stores a 2D matrix in a flat 1D buffer and accesses it using computed indices.
def idx_row_major(L1, U1, L2, U2, i, j):
N2 = U2 - L2 + 1
return (i - L1) * N2 + (j - L2)
def make_matrix_row_major(L1, U1, L2, U2):
N1 = U1 - L1 + 1
N2 = U2 - L2 + 1
# Fill A[i][j] = 10*i + j for clarity
buf = [0] * (N1 * N2)
for i in range(L1, U1 + 1):
for j in range(L2, U2 + 1):
buf[idx_row_major(L1, U1, L2, U2, i, j)] = 10 * i + j
return buf
if __name__ == "__main__":
L1, U1 = 0, 1 # rows 0..1
L2, U2 = 0, 2 # cols 0..2
buf = make_matrix_row_major(L1, U1, L2, U2)
# Print buffer to show row-major layout
print(buf)
# Row-major traversal: i major, then j
order_row = []
for i in range(L1, U1 + 1):
for j in range(L2, U2 + 1):
order_row.append(buf[idx_row_major(L1, U1, L2, U2, i, j)])
print(order_row)
# Column-major traversal over the same row-major buffer
order_col = []
for j in range(L2, U2 + 1):
for i in range(L1, U1 + 1):
order_col.append(buf[idx_row_major(L1, U1, L2, U2, i, j)])
print(order_col)
Sample input: (none; values are in the program)
Exact output:
[0, 1, 2, 10, 11, 12]
[0, 1, 2, 10, 11, 12]
[0, 10, 1, 11, 2, 12]
Explanation: The flat buffer [0, 1, 2, 10, 11, 12] shows row 0 (0,1,2) then row 1 (10,11,12) laid out contiguously. Row-major traversal reads in the same order as stored. Column-major traversal over a row-major buffer jumps between rows, yielding a different sequence.
Model answer pointer: If asked to “derive the general address calculation for a k-dimensional array in row-major order”, structure your answer as: definitions (Lᵣ, Uᵣ, Nᵣ, base, w), define strides S_k=1, S_r=Π_{t=r+1} N_t, derive the linear index by mixed-radix counting, then multiply by w to get bytes; finally write the boxed formula and mention assumptions.
Common mistakes
- Swapping N₁ and N₂ in 2D formulas, or using row-major formula for a column-major language (and vice versa).
- Using bytes where elements are expected (multiplying twice by w or failing to multiply by w at all).
- Assuming all languages store multi-dimensional arrays contiguously; e.g., Java and typical C “array of pointers” are jagged and not a single block.
- Confusing index order A[i][j] vs A[j][i] and blaming the “storage order” for wrong results.
- Forgetting that element size w affects addresses but not the count of elements; mixing units (elements vs bytes).
- Believing that dynamic arrays never move; in reality, resizable arrays may reallocate, invalidating old addresses/pointers.
- Ignoring cache effects: iterating by columns on a row-major array can be much slower due to poor locality.
For your exam
- Short notes: contiguous vs jagged arrays; cache locality; alignment; pros/cons of row-major vs column-major; language defaults (C row-major, Fortran column-major). Keep each to 5–6 crisp points.
- Derivations: 1D address law; 2D row-major and column-major; general kD formula. Show step-by-step: sizes Nᵣ, strides Sᵣ, linear index, bytes. End with the final boxed formula and conditions.
- Numericals: Given base, bounds, w, compute address of A[i…] (carry units in bytes, show intermediate offsets in elements and bytes). Reverse problems: given address, find indices by dividing and modding by strides.
- Programs: Write a function to compute address; flatten a 2D array into 1D; demonstrate traversal orders. Include sample I/O and exact output. Python is acceptable if your university allows; else C-style pseudocode.
- Diagrams: 1D layout strip; 2D row-major and column-major linearizations; label base, w, Nᵣ, and offsets in elements.
- What full marks need: correct formulas, correct substitution with bounds, clear unit handling (elements vs bytes), correct explanation of storage order and strides, neat and labeled diagrams, mention of assumptions.
Quick check
- A 1D array B has L = 0, U = 7, w = 8 bytes, base = 2000. What is addr(B[5])?
- In row-major order for a 2D array with L₁=1..U₁=3 and L₂=1..U₂=4, what is the element stride (in elements) between successive rows?
- State the general row-major kD address formula in one line.
Answers: (1) 2000 + (5 − 0)·8 = 2040 bytes; (2) N₂ = U₂ − L₂ + 1 = 4, so stride between rows = 4 elements; (3) address(A[i₁]…[i_k]) = base + [ Σ_{r=1 to k} (i_r − L_r)·S_r ]·w with S_k=1 and S_r=Π_{t=r+1 to k} N_t.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?