Arrays: A Deep Dive
Definition: An array is a finite, ordered collection of homogeneous (similar) data elements stored in contiguous (adjacent) memory locations.
Key Properties:
| Property | Meaning | Implication |
|---|---|---|
| Finite | Contains a specific number of elements | Size declared at creation, cannot grow |
| Ordered | Elements stored in sequential indices | Direct access via index (0, 1, 2...) |
| Homogeneous | All elements same data type | Cannot mix int and string in same array |
| Contiguous | Adjacent memory locations | Enables O(1) random access via address formula |
Array Operations & Time Complexity
| Operation | Time Complexity | Notes |
|---|---|---|
| Access by Index | O(1) | Direct calculation — greatest strength |
| Search (Unsorted) | O(n) | Must check each element |
| Search (Sorted) | O(log n) | Binary search possible |
| Insert at End | O(1) | If space available |
| Insert at Beginning/Middle | O(n) | Must shift elements right |
| Delete at End | O(1) | Simply reduce size |
| Delete at Beginning/Middle | O(n) | Must shift elements left |
Representation and Address Calculation
Since arrays are stored contiguously, we can calculate the memory address of any element if we know the base address.
1. Linear Array (1D)
- Formula:
Address(A[K]) = Base(A) + w × (K - LB) - Base(A): Starting address of the array.
- w: Size of each element in bytes (e.g., 4 bytes for int).
- K: Index of the element to find.
- LB: Lower Bound (Starting index, usually 0).
Worked Example:
Given: Base = 1000, w = 4 bytes, LB = 0. Find Address of A[5]. Address(A[5]) = 1000 + 4 × (5 - 0) = 1000 + 20 = 1020
2. Two-Dimensional Array (2D)
A 2D array is a "Matrix" with Rows and Columns. In memory, it is still stored linearly.
| Storage Order | Description | Formula |
|---|---|---|
| Row-Major | Row by row (C, C++, Java) | Base + w × [N × (i - Lr) + (j - Lc)] |
| Column-Major | Column by column (Fortran, MATLAB) | Base + w × [M × (j - Lc) + (i - Lr)] |
(N = Number of Columns, M = Number of Rows, Lr/Lc = Lower Bounds)
Worked Example (Row-Major):
Given: A[3][4] array, Base = 2000, w = 2 bytes, LB = 0. Find Address of A[2][3]. N = 4 (columns) Address = 2000 + 2 × [4 × (2 - 0) + (3 - 0)] = 2000 + 2 × [8 + 3] = 2000 + 22 = 2022
3. Three-Dimensional Array (3D)
A 3D array is a collection of 2D arrays (Pages × Rows × Columns).
- Concept: Think of a book (Pages), where each page has a grid of text (Rows, Cols).
Sparse Matrices
Definition: A Sparse Matrix is a matrix where the majority of elements are zero. Problem: Storing a standard 100×100 matrix with only 10 non-zero values wastes 9,990 memory spaces. Solution: Store only the non-zero elements using a "Triple" representation.
Triple Representation
Store each non-zero element as a 3-tuple: (Row, Column, Value).
Example: A 4×4 matrix with 3 non-zero values:
| Row | Col | Value |
|---|---|---|
| 0 | 1 | 5 |
| 1 | 3 | 8 |
| 2 | 0 | 3 |
This stores 9 values instead of 16 — saving 43% memory. For large matrices the savings are enormous.
Special Matrices
| Type | Definition | Condition | Storage Savings | ||
|---|---|---|---|---|---|
| Diagonal | Non-zero only on main diagonal | A[i][j] = 0 if i ≠ j | Store only n elements | ||
| Tri-Diagonal | Values on main, super, and sub diagonal | ` | i - j | ≤ 1` | Store 3n - 2 elements |
| Lower Triangular | All above diagonal are zero | A[i][j] = 0 if i < j | Store n(n+1)/2 elements | ||
| Upper Triangular | All below diagonal are zero | A[i][j] = 0 if i > j | Store n(n+1)/2 elements |
Array Applications
| Application | How Arrays Are Used |
|---|---|
| Lookup Tables | Store precomputed values for O(1) access |
| Image Storage | Pixels stored as 2D/3D arrays (RGB) |
| Dynamic Programming | Memoization tables for subproblem solutions |
| Hash Tables | Underlying storage for key-value pairs |
| Matrices in ML | Feature vectors, weight matrices in neural networks |