How Arrays Are Stored in Memory
Before any array pattern makes sense, one fact has to be solid: an array is not a list of boxes scattered around memory with pointers between them. It is one continuous run of bytes. Every cost you will meet later — cheap access, expensive insertion, fixed size — falls out of that.
The address formula
Suppose int arr[5] starts at memory address 1000 and each int occupies 4 bytes. The elements sit end to end, so the CPU never has to search for element 3 — it computes where element 3 must be:
One multiplication and one addition, regardless of whether the array holds 5 elements or 5 million. That is what O(1) random access means, and no other basic data structure gives it to you this cheaply.
Why indexing starts at 0
Index 0 means zero elements away from the start. The formula is base + index x size, so the first element needs an offset of 0. One-based indexing would cost a subtraction on every single access.
What contiguity costs you
Contiguity buys fast reads, and it charges for everything else. The memory after your array belongs to something else, so the array cannot simply grow, and there is no gap in the middle to slide a new element into.
- Fixed size. The length is decided when the array is allocated. Growing means allocating a bigger block and copying everything across.
- Expensive insertion in the middle. To free index
i, every element fromionwards shifts one place right — up to n moves. - Expensive deletion in the middle. The hole has to be closed, so everything after it shifts left.
- Excellent cache behaviour. Neighbouring elements land in the same cache line, so a linear scan of an array is dramatically faster in practice than the same scan over a linked list, even though both are O(n).
Dynamic arrays: how ArrayList and vector grow
ArrayList in Java, vector in C++, list in Python and Array in JavaScript are all dynamic arrays: a fixed array underneath, plus a rule for what happens when it fills up. When capacity runs out, a larger array is allocated (typically 1.5x or 2x) and the contents are copied over.
A single append can therefore cost O(n). But because the capacity doubles, those expensive copies get rarer as the array grows: appending n elements costs O(n) work in total, so each append averages out to O(1). That average is called amortised O(1), and it is the honest answer to "what does push_back cost?" in an interview.
Say the word 'amortised'
If you know the final size, pre-size the container (new ArrayList<>(n), vec.reserve(n)). It removes the copies entirely — a genuinely useful optimisation, and a good thing to mention unprompted.
Key takeaways
- An array is one contiguous block; the address of any element is computed, never searched for.
- O(1) access is a consequence of contiguity plus uniform element size.
- Insertion and deletion away from the end are O(n) because elements must shift.
- Dynamic arrays give amortised O(1) append by doubling capacity and copying.
Frequently asked questions
Why is array access O(1) but linked list access O(n)?
An array computes an element's address with base + index x size, which is constant work. A linked list stores each node wherever memory is free and connects them with pointers, so reaching the nth node means following n links.
What is the difference between an array and an ArrayList?
An array has a fixed length set at creation and can hold primitives directly. An ArrayList wraps an array and reallocates a larger one when it fills, so it can grow — at the cost of some memory overhead and occasional copying.
Does an array always store elements of the same type?
In statically typed languages, yes, and that is what keeps the element size uniform. Python lists and JavaScript arrays appear to hold mixed types because they actually store references of uniform size, and the values themselves live elsewhere.
Test yourself on Arrays
Reading is not recall. Take a timed quiz on this topic solo, or share a room code and battle friends on it.
⚡ Start the Arrays quiz