Back to 20 Concepts
memory • Beginner
Contiguous Physical RAM Layout & O(1) Address Arithmetic
An array stores elements in adjacent, unbroken physical memory bytes. Finding any index i takes strictly O(1) time via the pointer arithmetic formula: Address(A[i]) = BaseAddress + i * sizeof(Type).
Intuitive Mental Model
The Street of Identical Townhouses: The first house is #100. Each house is exactly 8 meters wide. To visit house #5, you do not walk past houses 1, 2, 3, and 4; you calculate 100 + 5 * 8 = 140 meters and teleport directly to the door.
C / TypeScript ImplementationHardware & Algorithmic Standard
// Pointer arithmetic in C / Low-level systems:
// int arr[5] = { 10, 20, 30, 40, 50 }; // sizeof(int) = 4 bytes
// Base Address = 0x1000
// Address of arr[3]:
// 0x1000 + (3 * 4) = 0x100C -> Direct O(1) hardware CPU memory fetch!Key Architectural Takeaways
- •Constant Time Random Access: Accessing arr[0] and arr[1,000,000] takes the exact same number of CPU cycles.
- •Contiguity Requirement: Arrays cannot be fragmented across different RAM regions; they require a single contiguous free block in virtual memory.
- •0-Indexed Offset: The index represents the distance (offset) from the base memory pointer.
Common Coding Mistake
Assuming linked lists have similar cache performance to arrays because both represent sequences of data.
Optimal Solution
Remember that linked list nodes are scattered across arbitrary heap locations, causing severe CPU cache misses on every pointer hop.