Course contents
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.
01The 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.
02What 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).
03Dynamic 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.
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 Arrays solo, or share a room code and battle friends on it.