Dynamic Array Explained: The Resizing Trick Every Language Uses
- A dynamic array keeps a size and a capacity; append is O(1) as long as size stays below capacity, then triggers a resize.
- Most languages grow by 1.5x to 2x on resize: Go starts at 2x and tapers, Java uses 1.5x, Python uses ~1.125x.
- Amortized O(1) append holds because the geometric series of copy costs sums to less than 2n across n appends.
- Insert or delete at arbitrary positions is O(n) due to shifting; repeatedly inserting at index 0 inside a loop is an O(n²) trap.
- Go slices expose the internals directly as a pointer/length/capacity struct; forgetting to reassign after
appendis a classic bug. - Space overhead is at most 2x with a doubling factor; Java's
trimToSize()and C++'sshrink_to_fit()reclaim unused capacity when needed.
You have an array. It's full. You need one more slot.
In C, that's your problem. You declared the size upfront, the runtime allocated exactly that much memory, and the bytes right after your array belong to something else now. Another variable, maybe. Maybe the stack. Enjoy your segfault.
In Python, Java, JavaScript, Go, and basically every language you write daily, you're fine. You call append and go on with your life.
That's the dynamic array. The data structure you use every day without naming it. Python's list, Java's ArrayList, C++'s std::vector, Go's slice: all dynamic arrays under the hood. Understanding how they grow explains why your code behaves the way it does, and interviewers ask about this more than most candidates expect.
Static Arrays Are Fixed. That's the Whole Problem.
A static array is a contiguous block of memory with a fixed size. Ask for 10 slots, you get 10 slots. The runtime allocated exactly those 10 slots, and whatever lives after them is not negotiable.
Random access is O(1) because any element's address is just base + i * element_size. The CPU computes it in one instruction. Fast, simple, extremely literal.
The catch arrives when you fill the array and need one more element. You cannot grow in place. You allocate a new, larger block somewhere else in memory and copy everything over manually.
A dynamic array automates exactly that copy-and-move, hiding it behind an append interface that pretends the array was always big enough. Internally it tracks two numbers: size (elements actually stored) and capacity (slots available in the backing block). Appending is instant while size stays under capacity. The moment size catches up to capacity, the array grows.
It Doesn't Add One Slot. It Doubles.
When a dynamic array runs out of room, it doesn't allocate one more slot. That would be ruinously expensive. It multiplies capacity by some factor, between 1.25x and 2x depending on who wrote the runtime:
- Go slices: 2x for small slices (under 256 elements), then roughly 1.25x for larger ones
- Java
ArrayList: 1.5x (new_capacity = old + old >> 1) - C++
std::vector: the standard just says amortized O(1) append is required; most compilers use 1.5x or 2x - Python
list: a nervously conservative 1.125x per resize (new = old + old >> 3 + 6), a formula so cautious that Python would apparently rather resize 12 times than waste a single byte
Here's what 2x growth looks like from scratch:
append 1: size=1, capacity=1 → full, allocate capacity=2, copy 1 element
append 2: size=2, capacity=2 → full, allocate capacity=4, copy 2 elements
append 3: size=3, capacity=4 → fits, no copy
append 4: size=4, capacity=4 → full, allocate capacity=8, copy 4 elements
append 5: size=5, capacity=8 → fits, no copy
Resizes happen, but they become exponentially rarer as the array grows. The question is what all of them cost in aggregate.
Amortized O(1): Why Expensive Resizes Don't Actually Hurt
Every time the array doubles, it copies every element. That's O(n) work. A natural reaction is: "if append sometimes does O(n) work, how can anyone call it O(1)?"
It isn't O(1) on every single call. It's O(1) amortized, meaning the average cost across any n appends is O(1) per operation. That's a different claim, and a true one.
With 2x growth, you resize at sizes 1, 2, 4, 8, 16... up to n. Add up all the copy work:
1 + 2 + 4 + 8 + ... + n/2 + n = 2n - 1
That geometric series caps at less than 2n. So n appends cost O(n) total, which is O(1) per append.
The doubling trick is what makes this work: by multiplying capacity, you push the next resize far away, and the copy cost gets diluted across many free appends in between. If you grew by 1 each time, the total copy work would be 1+2+3+...+n = O(n²). Different algorithm, wrong answer.
A useful mental model: each "free" append secretly pre-pays for its eventual copy. When the array doubles, every element's stored credit covers moving it. The accounting works out cleanly. CLRS Chapter 17.4 covers the formal version using the potential method if you want the receipts.
Every Operation, Ranked by How Much It'll Cost You
| Operation | Time | Notes |
|---|---|---|
| Access by index | O(1) | Direct memory calculation |
| Update by index | O(1) | Same as access |
| Append to end | O(1) amortized | Occasionally O(n) during resize |
| Insert at arbitrary position | O(n) | Shifts everything right |
| Delete at arbitrary position | O(n) | Shifts everything left |
| Search (unsorted) | O(n) | Linear scan |
| Search (sorted) | O(log n) | Binary search applies |
The O(n) insert and delete in the middle are the main pain point. If your algorithm repeatedly touches the front of the array, a dynamic array is the wrong tool. In practice though, the cache locality of contiguous memory makes arrays beat linked lists far more often than the complexity table suggests. See Array vs Linked List: The Tradeoff Every Interview Expects You to Know for the full comparison.
Space Complexity
A dynamic array is O(n) space, but the constant factor can be up to 2x. Right after a 2x resize, capacity is roughly twice the current size. With Java's 1.5x growth, you waste at most a third. Either way, it's bounded overhead, so we still call it O(n).
If memory matters after you stop growing, most languages let you trim: trimToSize() in Java, shrink_to_fit() in C++. Python doesn't expose this directly and trusts you'll be fine.
The API You Already Know (And the Trap You Keep Falling Into)
The resizing logic is invisible. Here's the surface you actually touch:
# Python nums = [] nums.append(1) # amortized O(1) nums.insert(0, 99) # O(n), shifts everything right nums.pop() # O(1), from the end nums.pop(0) # O(n), removes from front and shifts left
// Java List<Integer> nums = new ArrayList<>(); nums.add(42); // amortized O(1) nums.add(0, 42); // O(n), inserts at index 0 nums.remove(nums.size() - 1); // O(1), from the end
// JavaScript const nums = []; nums.push(1); // amortized O(1) nums.unshift(1); // O(n), inserts at index 0 nums.pop(); // O(1) nums.shift(); // O(n), removes from index 0
// Go: slices show you the seams nums := []int{} nums = append(nums, 1) // amortized O(1) // Insert at index i (no built-in, assemble manually): nums = append(nums[:i+1], nums[i:]...) nums[i] = val
Go slices deserve a closer look because they bite people who aren't paying attention. A slice is a three-word struct: a pointer to the backing array, a length, and a capacity. When append exceeds capacity, Go allocates a new backing array and returns a fresh slice header pointing to it.
That's why you must write nums = append(nums, val), not just append(nums, val). If you drop the return value, you're writing into the old backing array, which Go has already replaced. No error. No warning. Just quietly wrong output and a confusing debugging session later that afternoon.
What to Actually Say When They Ask About This
Dynamic arrays show up in interviews constantly, usually without introduction. A few things that prevent avoidable mistakes:
Indexing is O(1). Treat it like a free operation. Many problems that look like they need a linked list or deque are cleaner with index arithmetic. Two-pointer problems are built entirely on this: scan from both ends using indices, no pointer chasing.
Appending to the end is cheap. Inserting at the front is not. If your approach requires repeated insert(0, ...) or unshift, the runtime is O(n²) and something's wrong with the approach. Python's collections.deque, Java's ArrayDeque, or a different algorithm entirely is the fix.
Build output incrementally with appends, then return. Don't pre-allocate a buffer with a guessed size. Just append and let the dynamic array handle it. The amortized cost is the same as perfect pre-allocation. That said, if you know the final size upfront, make([]int, 0, n) in Go or new ArrayList<>(n) in Java signals to your interviewer that you understand what's happening underneath. Small thing, noticed.
In-place manipulation exploits O(1) index access. Reversing, rotating, two-pointer partitioning, cyclic sort: all of these work because any slot is reachable in constant time.
Know which operations are O(n) before you put them in a loop. Putting pop(0) inside a for-loop on a Python list is O(n²) disguised as O(n). Same with insert(0, ...) in a loop. You wrote a quadratic algorithm, confidently. The fix is usually to reverse the output at the end, iterate in a different order, or use deque. Interviewers notice. They always notice.
For the formal complexity analysis behind all of this, Dynamic Array Time Complexity: What Every append() Is Actually Doing and Amortized Analysis: When One Expensive Operation Pays for Itself go deeper into the math.
If you want to practice explaining these tradeoffs out loud under pressure, SpaceComplexity runs voice-based mock interviews where this comes up directly: "what's the time complexity of appending to a list?" Saying "amortized O(1)" earns you a point. Explaining the doubling argument in 30 seconds earns you a lot more.