Foundational Mental Model
Arrays & Memory Architecture
Why this lesson right now?Adaptive Pedagogy
You encountered memory indexing and boundary traps in recent problem attempts. This 15-minute interactive module directly targets those exact gaps before advancing to downstream tree and graph traversals.
### What is an Array? An **Array** is a linear data structure that stores elements of the same data type in **contiguous memory blocks**.
Core Superpowers: - **Instant Random Access**: Because elements are laid out back-to-back in RAM, the computer accesses any element at index `i` in **O(1) constant time** using the memory address formula: $$\text{Address}(i) = \text{BaseAddress} + (i \times \text{ElementSize})$$ - **Cache Locality**: CPU cache lines prefetch contiguous array chunks into L1/L2 cache, resulting in blazing fast iterations compared to linked lists.
Tradeoffs to Remember: - **Fixed Size / Resizing Cost**: Dynamic arrays (like Python `list` or C++ `std::vector`) double their capacity when full, triggering an $O(N)$ reallocation. - **Insertion / Deletion Overhead**: Inserting or removing at the start or middle requires shifting $O(N)$ elements.
Time Complexity
Access: O(1) | Search: O(N) | Insertion: O(N)
Space Complexity
O(N) contiguous memory