Why item one million is as quick to reach as item one
An array is a row of same-sized items stored side by side in one unbroken block of memory, each numbered by an index starting at 0. Nothing sits between items, so the computer calculates where one is instead of searching.
Picture a list of 1,000,000 temperature readings, each a 4-byte number. Reading index 999,999 takes the same single step as reading index 0, so access is O(1), constant time no matter how long the array is.
Data structures · 2 of 112 / 3
Arrays
Real-life use case
Every photo on your screen is one long row of pixels
When your phone shows a photo, the decoded image sits in memory as an array of pixels, stored row after row. A 4000-pixel-wide photo puts the pixel at column x, row y at index y × 4000 + x.
So an editing app that changes one pixel computes its index and jumps straight there, skipping millions of others. Python lists, Java arrays and JavaScript arrays are arrays underneath too.
Data structures · 2 of 113 / 3
Arrays
How it helps
Position times item size gives the exact memory address
Memory is a numbered row of bytes, and the array remembers only where its block starts, the base address. Since every item has the same size, item i begins exactly i × size bytes after the start: one multiply and one add, whatever i is.
The price comes when you change the middle. Inserting at index 0 of a 1,000-item array shifts all 1,000 items one place right: O(n) work.
When a growable (dynamic) array fills up, it copies everything into a block about twice as big. Those copies are rare, so appending to the end still averages O(1).
What it’s forFinds where any item of an array lives in memory, from its position alone.
address(i) = base + i × size
base
memory address where the array's first item (index 0) starts
i
the index of the item you want, counting from 0
size
bytes per item, e.g. 4 for a 32-bit integer
What it givesThe exact byte where item i begins, computed in one step for any i.