Arrays and contiguous memory
Arrays store elements in one contiguous block, which is why indexing is O(1) — the address is just base + index × size — and why inserting in the middle is O(n), since everything after the insertion point has to shift.
That trade-off drives a surprising number of interview answers. Reach for an array when you index often and mutate rarely; reach for a linked list or hash map when the reverse is true.
Time and space complexity
| Operation | Time | Notes |
|---|---|---|
| Access by index | O(1) | Direct address arithmetic |
| Search (unsorted) | O(n) | Must scan every element |
| Search (sorted) | O(log n) | Binary search applies |
| Insert / delete at end | O(1) amortised | Occasional resize copies n elements |
| Insert / delete at start or middle | O(n) | Shifts all following elements |
How to use this visualizer
Select an array operation track to load its pseudocode.
Step through and watch which cells are read versus written.
Note the shift cascade on a middle insert — that cascade is the O(n).
Compare an append against a middle insert to feel the difference.
Frequently asked questions
Because elements sit in contiguous memory and every element has the same width, the address of index i is computed arithmetically as base + i × elementSize. No traversal is involved, so the cost does not grow with the array length.
A dynamic array grows by doubling its capacity. Most pushes write into spare capacity in O(1); occasionally one push triggers an O(n) copy into a larger buffer. Spread across n pushes, the copies total O(n), so the average cost per push is constant — that average is what "amortised" describes.
Use an array when you index randomly, iterate frequently, or care about cache locality — contiguous memory makes traversal dramatically faster in practice. Use a linked list when you insert and delete at known positions constantly and never need random access, since those operations are O(1) once you hold the node.