Arrays & Memory
Overview
An array is a contiguous block of memory where elements of the same size are stored sequentially. Because the memory is contiguous, the address of any element can be calculated instantly using simple math: base_address + (index * element_size).
Arrays provide O(1) random access, meaning you can retrieve the 1st or the 1,000,000th element in the exact same amount of time. They are the foundational building block for more complex data structures like strings, dynamic arrays, and hash tables.
Where used: Implementing buffers, queues, and stacks, Serving as the underlying storage for higher-level structures like Python lists or Java ArrayLists
Why learn this
- Arrays are the most commonly tested data structure in coding interviews.
- Understanding memory layout (contiguous vs. scattered) explains why arrays are faster than linked lists for iteration due to CPU cache locality.
- It builds the intuition for why inserting or deleting in the middle of an array costs O(n): you have to shift all subsequent elements.
Aha moment
arr = [10, 20, 30]
# Memory layout:
# Address 0x00: 10
# Address 0x04: 20
# Address 0x08: 30
# Accessing arr[2] doesn't scan the list. It computes: 0x00 + (2 * 4) = 0x08.Prediction: The computer scans through 10 and 20 to find 30.
Common guess: It has to walk through the list to know where the 3rd item is.
Arrays are fundamentally just blocks of math. The index is not a label; it's a distance. 'Index 2' literally means '2 elements away from the start'. This strict geometric layout is what gives arrays their O(1) speed.
Common mistakes
- Confusing index and value: Beginners often mix up 'i' (the position) and 'arr[i]' (the data at that position). An index is just an offset from the start of memory.
- Out of bounds errors: Because arrays are zero-indexed, an array of size n goes from index 0 to n-1. Accessing index n accesses unallocated memory or throws an error.
- Assuming insertion is O(1): While overwriting an existing index is O(1), inserting a new element at index 0 requires shifting every single existing element one spot to the right, which is O(n).
Glossary
- contiguous block
- An uninterrupted sequence of memory spaces.
- CPU cache locality
- The tendency of a computer processor to access memory locations that are near each other.
Recall questions
- Why is accessing an array element by index an O(1) operation?
- What is the time complexity of inserting an element at the beginning of an array, and why?
- Why are arrays generally faster to iterate over than linked lists, even though both are O(n)?
Understanding checks
If an array starts at memory address 1000 and holds 32-bit (4-byte) integers, what is the memory address of the element at index 5?
1020. The formula is base + (index * size) = 1000 + (5 * 4) = 1000 + 20 = 1020.
This math is the exact reason arrays offer O(1) access. The CPU doesn't search; it computes the exact physical location.
You have a Python list containing 10,000 items. Why does `list.pop(0)` feel sluggish compared to `list.pop()`?
`pop()` removes the last item, which is O(1). `pop(0)` removes the first item, meaning the remaining 9,999 items must all be shifted left by one index in memory, making it O(n).
Operations that change the size of the array at the front or middle trigger a cascade of memory shifts. Understanding this prevents writing accidentally quadratic loops.
Practice tasks
Reverse an array in place
Given an array, write a loop that swaps the elements at the ends, moving inwards, until the array is reversed. Do not create a new array.
Continue learning
Previous: Big-O Notation
Next: In-Place Operations
Next: 2D Arrays & Matrices