Foundation · Module 3 · Lesson 1
Array memory model
Contiguous storage, indexes, resizing, and shifting.
Lesson 13 of 123
1d streakInteractive Visualization
See how array memory model works
Change the inputs, run an operation, and connect each visible state change to the explanation below.
Interactive data structure
Change the structure and watch the operation
Try an operation and connect the visible movement to its runtime cost.
Contiguous Storage & The O(1) Address Formula
An Array is a linear collection of elements of the same type stored in one unbroken, contiguous block of physical memory. Because every item occupies identical bytes and sits immediately adjacent to its neighbors, the computer does not traverse through intermediate elements to find index i—it calculates the exact memory location in a single mathematical step.
Base Address = 0x1000 | Element Size = 4 bytes (32-bit int)
Index: 0 1 2 3
+----------+ +----------+ +----------+ +----------+
Value: | 10 | | 20 | | 30 | | 40 |
+----------+ +----------+ +----------+ +----------+
Address: 0x1000 0x1004 0x1008 0x100C
Offset: +0 bytes +4 bytes +8 bytes +12 bytes
Address Formula:
Address(nums[i]) = BaseAddress + (i * ElementSize)To read nums[3], the CPU calculates 0x1000 + (3 * 4) = 0x100C in 1 single clock cycle. This is why array indexing is strictly O(1). It also explains why arrays are 0-indexed: the index is simply the displacement offset from the starting address (0 * 4 = 0 byte offset for the first element).
Why Arrays Beat Linked Lists: CPU Cache Lines & Spatial Locality
nums[0], the CPU automatically pulls nums[0] through nums[15] into ultra-fast L1 cache memory (~1 ns latency). Sequential iteration reads the remaining 15 numbers instantly with zero RAM stalls. Linked lists scatter nodes across heap RAM, causing repeated CPU cache misses (~50-100 ns latency per hop).Core Operations & The Penalty of Shifting
| Operation | Time Complexity | Aux Space | Why it takes this time |
|---|---|---|---|
| Read index: arr[i] | O(1) | O(1) | Instant address calculation (Base + i * Size) |
| Update index: arr[i] = val | O(1) | O(1) | Direct memory write to computed address |
| Append at tail (with room) | O(1) | O(1) | Writes to base + size * elementSize; increments size |
| Insert at head (index 0) | O(n) | O(1) | Every existing element must shift 1 slot to the right |
| Insert at middle (index k) | O(n) | O(1) | All elements from index k to n-1 must shift right |
| Delete from head (index 0) | O(n) | O(1) | All remaining elements must shift 1 slot to the left |
| Linear Search (unsorted) | O(n) | O(1) | Must check elements one-by-one until found |
| Binary Search (sorted) | O(log n) | O(1) | Halves search space on each comparison |
Initial Array: [ 10 ][ 20 ][ 30 ][ 40 ][ ] (size = 4, capacity = 5)
Insert 99 at index 1:
Step 1: Shift 40 right -> [ 10 ][ 20 ][ 30 ][ ][ 40 ]
Step 2: Shift 30 right -> [ 10 ][ 20 ][ ][ 30 ][ 40 ]
Step 3: Shift 20 right -> [ 10 ][ ][ 20 ][ 30 ][ 40 ]
Step 4: Write 99 -> [ 10 ][ 99 ][ 20 ][ 30 ][ 40 ] (size = 5)
Notice: Every single element after index 1 had to be moved! That is why middle insertion is O(n).Architectural Boundary · Do Not Confuse
Arrays: Contiguous Blocks
Linked Lists: Node Pointers
Arrays provide instant O(1) index access and maximum cache efficiency, but pay O(n) shifts to insert in the middle. Linked lists can insert in O(1) with pointer rewiring, but require O(n) sequential steps to find any index.
Static vs Dynamic Arrays: Why Append is Amortized O(1)
A Static Array has a fixed capacity chosen at creation time that can never grow. A Dynamic Array (ArrayList in Java, vector in C++, list in Python) automatically resizes itself when full by allocating a new array of double the capacity and copying existing elements over.
Insert 1: [ 10 ] (Capacity 1 - Full)
Insert 2: [ 10 | 20 ] (Doubled to Capacity 2 - Full)
Insert 3: [ 10 | 20 | 30 | _ ] (Doubled to Capacity 4 - 1 copy + 1 insert)
Insert 4: [ 10 | 20 | 30 | 40 ] (Capacity 4 - Instant O(1) insert)
Insert 5: [ 10 | 20 | 30 | 40 | 50 | _ | _ | _ ] (Doubled to Capacity 8)
The Math Behind Amortized O(1):
To insert N elements:
- Regular insertions: N operations
- Total resizing copies: 1 + 2 + 4 + ... + N/2 = N - 1 operations
- Total Work for N insertions: N + (N - 1) ≈ 2N operations
- Average Work Per Insertion: 2N / N = 2 = O(1) Amortized Time!Active Recall Checkpoint
What happens if a dynamic array increases its size by a constant amount (e.g., +10 items each time) instead of doubling (2x)?
Hint: Calculate how often resizing occurs when inserting N elements.
Show answer & explanation
If capacity grows by +K, resizing occurs N/K times, causing 1K + 2K + 3K + ... copies = O(n²) total time! Geometric doubling (2x) is required to guarantee O(1) amortized append.
Cost Model
Complexity & Trade-offs
When to use it
- Compact ordered storage with frequent indexed reads.
- Cache-friendly scans, matrices, lookup tables, and dynamic-programming state.
- Backing storage for heaps, dynamic arrays, stacks, and ring buffers.
Common mistakes
- Using length as the last valid index instead of length - 1.
- Treating middle insertion or deletion as constant time.
- Ignoring the occasional O(n) copy performed during dynamic-array growth.
Practice prompts
- Calculate the byte address of index 7 for a 4-byte element.
- Trace an insertion at index 2 and mark every shifted value.
- Compare a fixed Java array with ArrayList growth behavior.
Mastery check