Arrays
An array stores elements in contiguous memory, so any element can be reached in O(1) using its index.
Address Calculation
1-D: Loc(A[i]) = Base + w × (i − LB)
2-D (m × n), row-major: Loc(A[i][j]) = Base + w × [ n(i − LR) + (j − LC) ]
2-D (m × n), column-major: Loc(A[i][j]) = Base + w × [ m(j − LC) + (i − LR) ]
Example: int A[5][4], Base = 1000, w = 4, row-major, LB = 0
Loc(A[2][3]) = 1000 + 4 × (4×2 + 3) = 1000 + 44 = 1044
Insertion and Deletion
#include <stdio.h>
int main() {
int a[10] = {10, 20, 30, 40, 50}, n = 5;
int pos = 2, val = 25;
for (int i = n; i > pos; i--) a[i] = a[i - 1]; // shift right
a[pos] = val; n++;
int del = 4; // delete index 4
for (int i = del; i < n - 1; i++) a[i] = a[i + 1];
n--;
for (int i = 0; i < n; i++) printf("%d ", a[i]);
return 0;
}
10 20 25 30 50
Sparse Matrix (Triplet Form)
When most elements are zero, store only (row, column, value) triplets to save space.
Track your progress through the Data Structures course