Arrays

An array stores elements in contiguous memory, so any element can be reached in O(1) using its index.

Address Calculation

Text
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

C
#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