What Is an Array? The Data Structure Behind Every Interview
- Array indexing is O(1) because every element sits at a predictable memory offset — one multiplication, one addition, no traversal.
- Insertion and deletion in the middle are O(n) because every element after the target must shift one slot; the end is O(1) amortized.
- Dynamic arrays resize by copying to a larger block; growth factors differ (Python ~1.125×, Java 1.5×, C++ 2×) but all amortize to O(1) append.
- Cache locality gives arrays a 5-10× speed advantage over linked lists in sequential traversal, even when both are O(n) asymptotically.
- Two pointers, sliding window, binary search, and prefix sums all run on direct index arithmetic — understanding arrays unlocks every major pattern.
shift(),unshift(), andpop(0)are O(n) traps that look constant-time but shift every element behind the scenes.
You've looped over lists of numbers hundreds of times without thinking about it. Probably wrote for i in range(len(arr)) at 2am, hit submit, moved on. You were using an array. You've been using arrays since you wrote your first program. And you've never actually thought about how they work. This is the post.
An Array Is Not Just a List
The textbook definition skips the interesting part. An array is not just an ordered collection. It's a contiguous block of memory where every element sits at a predictable offset from the start.
"Contiguous" is doing a lot of work in that sentence. If you know where the array starts and what type it holds, you can compute the exact memory address of any element with one arithmetic expression:
address = base_address + (index × element_size)
For a 32-bit integer array starting at address 1000: element 0 lives at 1000, element 1 at 1004, element 2 at 1008. No pointer chasing. No traversal. One multiply and one add, and the CPU knows exactly where to look.
One address calculation. That's the whole trick.
This is why array access is O(1). Not magic. Arithmetic.
Indices Start at Zero and That Will Bite You
Most interview languages make this feel instant:
nums = [10, 20, 30, 40, 50] print(nums[2]) # 30, one address calculation
const nums: number[] = [10, 20, 30, 40, 50]; console.log(nums[2]); // 30, same deal
One thing developers consistently get wrong under pressure: indices start at zero. Element 0 is first. Element n-1 is last. This sounds obvious. It stops being obvious at the 40-minute mark of a coding interview when you're also managing a two-pointer and narrating your approach and wondering if your webcam is at a flattering angle.
A shocking number of off-by-one bugs in interviews happen to people who "knew" this cold.
Where Arrays Actually Slow Down
Here's the table worth memorizing:
| Operation | Time Complexity | Why |
|---|---|---|
| Access by index | O(1) | Single address calculation |
| Search (unsorted) | O(n) | May need to check every element |
| Search (sorted) | O(log n) | Binary search halves the space each step |
| Insert / delete at end | O(1) | No shifting required |
| Insert / delete in middle | O(n) | Every element after must shift |
The slow operations are always about shifting. Insert at position i and every element from i to the end has to move one slot forward. Insert at position 0 in a million-element array? That's a million copy operations. Arrays are fast readers and slow writers. Great at the end. Miserable in the middle.
Static Allocates. Dynamic Panics, Then Copies.
Two flavors exist, and most modern languages give you the dynamic version while hiding what it actually does.
A static array is honest. Fixed size at creation, memory allocated upfront, and when it fills up, that's your problem. C's int arr[100] is the canonical example.
A dynamic array (Python's list, Java's ArrayList, JavaScript's Array, C++'s std::vector) pretends to grow magically. The actual mechanism is slightly awkward:
- When the array fills, allocate a new, larger block.
- Copy every existing element to the new block.
- Free the old block.
- Now add the new element.
Step 2 is O(n). That sounds bad. But languages minimize how often this happens by growing aggressively. CPython grows by roughly 12.5% per resize; Java's ArrayList by 50%; C++ vectors typically double. Doubling is the most popular strategy, and here's why it's clever:
Resize events happen at sizes 1, 2, 4, 8, 16... The total copying work across all of them is 1 + 2 + 4 + ... + n, which sums to roughly 2n. Spread across n insertions, that's O(1) per insertion on average. The expensive resizes are rare enough to average out.
This is what "O(1) amortized append" means. The word "amortized" is not decorative. It's telling you the math works out across many operations even if individual ones are expensive.
An array of n elements uses O(n) space with zero per-element overhead. Unlike a linked list, there's no pointer stored next to each value. Just 4n bytes for n 32-bit integers. That density has consequences.
Arrays Beat Linked Lists by 5x and the Reason Is Embarrassing for Linked Lists
O(1) random access is the obvious advantage. But there's a second one that never shows up in Big-O analysis at all: cache locality.
Modern processors don't fetch one value from memory. They fetch 64 bytes at a time, a full cache line. For 32-bit integers, that's 16 elements loaded in one shot. When you access nums[0], the CPU silently loads nums[1] through nums[15] at the same time. When you then access nums[1], it's already in cache. Free. Same for nums[2] through nums[15].
A linked list doesn't get this. Each node can live anywhere in memory. Every pointer hop is a fresh load from an unknown address. The hardware prefetcher, which tries to predict what memory you'll need next based on your access patterns, cannot follow random pointers. It gives up. Every step costs a full memory fetch.
Real benchmarks consistently show arrays running 5 to 10 times faster for sequential traversal, even though Big-O treats both as O(n). The asymptotic complexity is the same. The actual performance is not.
You don't need to bring this up in most interviews. But knowing it explains why interviewers prefer array-backed solutions when a linked list would technically also work.
Every Interview Pattern You're Studying Lives on Top of Arrays
Almost every coding problem opens with "given an array." That's not a coincidence. The patterns are creative ways to move indices around on top of O(1) access.
Two pointers. Two indices, usually one at each end, moving toward each other or both in the same direction. Used for sum targets, removing duplicates, and container-with-most-water. O(n) time, no extra space. The two pointer technique covers when each variant applies.
Sliding window. A left and right index defining a window over the array, expanding or contracting as you scan forward. Used for longest substrings and minimum subarray sums. See sliding window algorithm for the full pattern.
Binary search. Works on sorted arrays. Each step computes a midpoint index and halves the search space. O(log n) because every index lookup is free. See binary search invariant for the loop invariant approach.
Prefix sums. Build an auxiliary array where prefix[i] holds the sum from index 0 to i. Then any subarray sum becomes an O(1) subtraction. You pay O(n) upfront to buy free queries forever.
In-place operations. Use a write pointer trailing behind your read pointer to overwrite elements in a second pass. Common for "move zeroes to end" and "rotate array" without allocating extra space.
Array indices are just numbers. Add them, subtract them, take midpoints, use two simultaneously. That flexibility is why arrays are the canvas everything else gets built on.
The O(n) Traps Hiding in Plain Sight
# Python nums = [1, 2, 3] nums.append(4) # O(1) amortized nums.insert(0, 0) # O(n), shifts everything nums.pop() # O(1) nums.pop(0) # O(n), shifts everything
// Java: static int[] nums = new int[5]; nums[0] = 1; // Java: dynamic List<Integer> list = new ArrayList<>(); list.add(1); // O(1) amortized list.add(0, 0); // O(n) list.remove(list.size() - 1); // O(1)
// TypeScript const nums: number[] = []; nums.push(1); // O(1) amortized nums.unshift(0); // O(n), shifts everything nums.pop(); // O(1) nums.shift(); // O(n), shifts everything
shift(), unshift(), and pop(0) are O(n), not O(1). Every element after position 0 has to move. If you implement a queue by pushing to the end and shifting from the front, your queue has O(n) dequeue. It works. It's wrong. Reach for a deque or a purpose-built queue structure when you need front-and-back operations.
The syntax looks constant. The cost is not. That gap between how something looks and how it performs is exactly the kind of thing interviewers are probing.
What You Actually Need to Know
- Index access is O(1) because it's a single address calculation, not a traversal. That's the whole model.
- Insertion and deletion in the middle are O(n) due to shifting. Operations at the end are O(1) amortized.
- Dynamic arrays resize by copying everything to a larger block. Growth factors differ by language (Python ~1.125x, Java 1.5x, C++ 2x) but all achieve O(1) amortized append.
- Cache locality makes sequential array traversal 5 to 10 times faster than linked lists in practice, regardless of asymptotic parity.
- Two pointers, sliding window, binary search, and prefix sums all run directly on array index arithmetic.
- Front-of-array operations are O(n) traps disguised as O(1) method calls.
If you want to see how well this holds under actual interview conditions, SpaceComplexity runs voice-based DSA mock interviews with rubric-based feedback. There's a real gap between knowing array insertion is O(n) and explaining it clearly when someone is watching the clock.