Loading learning content...
You're building a program that reads user input—a list of items, perhaps. You have no idea how many items the user will provide. Maybe 3, maybe 3 million. You need an array's O(1) access speed, but you can't predict the size upfront. What do you do?
This seemingly simple scenario stumps static arrays. Their fixed-size nature means you'd have to either guess a maximum (wasteful and potentially incorrect) or manually implement resizing logic (tedious and error-prone).
The dynamic array solves this problem elegantly. It provides the illusion of an array that grows automatically as you add elements, while internally managing all the complexity of memory allocation and reallocation. Understanding how this works—and the clever engineering that makes it efficient—is essential knowledge for any serious programmer.
By the end of this page, you will understand the internal architecture of dynamic arrays, how they manage capacity vs size distinction, the mechanics of automatic resizing, and why this seemingly simple data structure is found in nearly every programming language as the default 'list' or 'array' type.
Let's establish a precise definition:
Definition:
A dynamic array (also called a growable array, resizable array, or array list) is an array data structure that automatically manages its own memory, growing in capacity as elements are added, while maintaining O(1) amortized time for element access and append operations.
Let's break down what this means:
The key insight:
A dynamic array is not a fundamentally different data structure from a static array. It is a wrapper around a static array that adds automatic resizing logic. Internally, a dynamic array always uses a plain static array for storage. When that internal array fills up, the dynamic array:
This is exactly the manual reallocation pattern we discussed — automated and optimized.
Common names across languages:
| Language | Name | Example Usage |
|---|---|---|
| Python | list | my_list = [1, 2, 3] |
| JavaScript | Array | let arr = [1, 2, 3] |
| Java | ArrayList<T> | ArrayList<Integer> list = new ArrayList<>() |
| C++ | std::vector<T> | std::vector<int> vec = {1, 2, 3} |
| C# | List<T> | List<int> list = new List<int>() |
| Rust | Vec<T> | let v: Vec<i32> = vec![1, 2, 3] |
| Go | slice | s := []int{1, 2, 3} |
| Swift | Array | var arr = [1, 2, 3] |
In most modern languages, the 'default' array or list type is actually a dynamic array. Python's list, JavaScript's Array, Java's ArrayList — these are all dynamic arrays. True static arrays (fixed-size at creation) are often a secondary feature or require explicit syntax. Dynamic arrays won the default position because they're more flexible for general programming.
To understand how dynamic arrays work, we need to examine their internal structure. A dynamic array maintains three essential pieces of information:
1. The underlying static array (storage)
This is where elements are actually stored — a plain static array with some fixed capacity. The dynamic array 'owns' this array and can replace it when needed.
2. Capacity (physical size)
The maximum number of elements the current underlying array can hold. This is the size of the internal static array. Capacity ≥ Size always.
3. Size (logical size)
The number of elements actually stored in the array — how many slots are 'in use'. This is what users of the dynamic array see as the array's length.
Visualizing the structure:
Imagine a dynamic array with size 5 and capacity 8:
Capacity = 8
Size = 5
0 1 2 3 4 5 6 7
+----+----+----+----+----+----+----+----+
Data: | 10 | 25 | 33 | 47 | 52 | — | — | — |
+----+----+----+----+----+----+----+----+
[────── Size = 5 ──────][── Unused ──────]
[───────────── Capacity = 8 ─────────────]
The gap between size and capacity is the 'buffer' that allows O(1) appends. When size < capacity, adding an element is just writing to the next slot and incrementing size — no allocation needed. Only when size = capacity (buffer exhausted) does a resize occur.
The append operation (adding an element to the end) is where the magic of dynamic arrays happens. Let's trace through exactly what occurs:
Case 1: Size < Capacity (Fast Path)
When there's available space, append is trivially O(1):
Before: Size = 5, Capacity = 8
[10, 25, 33, 47, 52, —, —, —]
Append(99):
1. Write 99 to index 5 (the slot at position 'size')
2. Increment size to 6
3. Done!
After: Size = 6, Capacity = 8
[10, 25, 33, 47, 52, 99, —, —]
This is a single array write plus an increment — O(1) with tiny constant factors.
Case 2: Size = Capacity (Slow Path — Resize Required)
When the array is full, append triggers a resize:
Before: Size = 8, Capacity = 8 (full!)
[10, 25, 33, 47, 52, 99, 77, 81]
Append(100):
1. Array is full! Cannot write directly.
2. Allocate NEW array with larger capacity (e.g., 16)
3. Copy all 8 elements to new array
4. Write 100 to index 8 in new array
5. Free the old 8-element array
6. size = 9, capacity = 16
After: Size = 9, Capacity = 16
[10, 25, 33, 47, 52, 99, 77, 81, 100, —, —, —, —, —, —, —]
The resize operation in detail:
data pointer to point to the new array. Update the capacity variable.A single resize operation is O(n) — you must copy every existing element. For an array with 1 million elements, that's 1 million copy operations. This seems problematic until you understand amortized analysis, which we'll cover in the next page. Spoiler: the key is that resizes happen infrequently.
When a dynamic array needs to grow, how much larger should the new array be? This question is critical — the wrong answer leads to poor performance.
The naive approach: Grow by 1
What if we just add one slot each time we need more space?
Capacity progression: 1 → 2 → 3 → 4 → 5 → 6 → ...
This seems memory-efficient — we never have more than 1 unused slot. But analyze the cost of appending n elements:
Total copies: 0 + 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 = O(n²)
This is catastrophic. Appending n elements takes O(n²) time — each append is O(n) on average!
The smart approach: Geometric growth
Instead of adding a constant amount, multiply capacity by a constant factor (typically 2, sometimes 1.5):
Capacity progression: 1 → 2 → 4 → 8 → 16 → 32 → 64 → ...
Now analyze the cost of appending n elements (with n = 32 for example):
Total copies: 1 + 2 + 4 + 8 + 16 + 32 = 63 < 2n
For n appends, we do O(n) total copying work. Each append is O(1) amortized!
| Elements Added | Growth by 1 (total copies) | Doubling (total copies) |
|---|---|---|
| 10 | 45 | 15 |
| 100 | 4,950 | 127 |
| 1,000 | 499,500 | 1,023 |
| 10,000 | 49,995,000 | 16,383 |
| 1,000,000 | 499,999,500,000 | 1,048,575 |
The mathematical insight: with doubling, after any resize, at least half the array is newly allocated space. This means the next resize won't happen until we've added at least as many elements as we just copied. Each element is copied at most O(log n) times total across all resizes, not O(n) times. This is the key to amortized O(1) performance.
Different dynamic array implementations use different growth factors. Each choice represents a trade-off:
Growth factor of 2.0 (doubling):
Most common and easiest to analyze. After a resize, the array is 50% full. Maximum memory overhead: 100% (you might have an array of capacity 2n holding only n+1 elements just after a resize).
Growth factor of 1.5:
Used by some implementations (e.g., Microsoft's std::vector, older Java ArrayList). Reduces maximum memory overhead to 50% but requires more frequent resizes.
Golden ratio (~1.618):
Used in some specialized implementations. Has interesting mathematical properties related to memory allocation patterns.
Variable/adaptive:
Some implementations adjust the growth factor based on current size (smaller factor for larger arrays to avoid massive over-allocation).
| Growth Factor | Resize Frequency | Memory Overhead | Use Case |
|---|---|---|---|
| 2.0 | Low (log₂n resizes) | Up to 100% | General purpose, performance focus |
| 1.5 | Medium (log₁.₅n resizes) | Up to 50% | Memory-conscious applications |
| 1.25 | High (log₁.₂₅n resizes) | Up to 25% | Very memory-constrained |
| 1.1 | Very high | Up to 10% | Rarely used (too many resizes) |
| 3.0+ | Very low | Up to 200%+ | Rarely used (too much waste) |
Real-world implementations:
The factor of 2 remains popular because:
Regardless of the exact growth factor, the principle remains: geometric growth (multiplying by some constant > 1) gives amortized O(1) append. Linear growth (adding a constant) gives O(n) per append. Any sane dynamic array implementation uses geometric growth.
Beyond append, dynamic arrays support all standard array operations, with complexity characteristics inherited from the underlying static array:
Access and Update: O(1)
Identical to static arrays. The underlying storage is a contiguous array, so index-based access remains constant time.
Insert at arbitrary position: O(n)
To insert at index i, all elements from i to size-1 must shift right by one position. In the worst case (insert at index 0), this is O(n).
Before: [10, 20, 30, 40, 50] size=5
Insert(1, 99): // insert 99 at index 1
Shift: [10, __, 20, 30, 40, 50]
Write: [10, 99, 20, 30, 40, 50] size=6
Delete at arbitrary position: O(n)
To delete at index i, all elements from i+1 to size-1 must shift left by one position. Similar to insert, worst case is O(n).
Delete from end (pop): O(1)
Just decrement size. The element's memory remains allocated (within capacity) but is no longer 'in' the array.
Prepend (insert at beginning): O(n)
Worst case of insert — every element must shift right.
| Operation | Time Complexity | Notes |
|---|---|---|
| Access by index | O(1) | Same as static array |
| Update by index | O(1) | Same as static array |
| Append (amortized) | O(1) | O(n) worst case during resize |
| Pop from end | O(1) | Just decrement size |
| Insert at index i | O(n) | Must shift n-i elements |
| Delete at index i | O(n) | Must shift n-i elements |
| Prepend (insert at 0) | O(n) | Must shift all elements |
| Search (unsorted) | O(n) | Must check each element |
| Search (sorted) | O(log n) | Binary search |
| Clear | O(1) or O(n) | Depends if elements need destruction |
A common mistake is assuming dynamic arrays are efficient for arbitrary insertions. They're not — only end operations are fast. If you need frequent insertions/deletions at arbitrary positions, consider a different data structure (linked list, balanced tree, etc.). Dynamic arrays optimize for end operations and random access.
We've focused on growth, but what about shrinking? When elements are removed, the capacity remains unchanged. This can lead to memory waste:
Scenario:
1. Build array to 1,000,000 elements (capacity ~1M)
2. Remove 999,990 elements
3. Array now has 10 elements but capacity for 1M!
Why don't dynamic arrays shrink automatically?
Avoiding thrashing: If the array repeatedly grows just past a threshold then shrinks below it, constant resize operations would kill performance. Hysteresis (delaying shrinking) prevents this.
Anticipating regrowth: Often when elements are removed, they're soon replaced. Keeping capacity avoids immediate re-expansion.
Predictable performance: Automatic shrinking makes remove operations unpredictably expensive. Explicit shrinking gives programmers control.
Simplicity: The grow-only policy is simpler to implement correctly.
Explicit shrinking:
Most dynamic array implementations provide an explicit "shrink to fit" or "compact" operation:
list.copy() creates a right-sized copy; no direct shrinkArrayList.trimToSize()std::vector::shrink_to_fit()Vec::shrink_to_fit()This operation reallocates the internal array to exactly match the logical size, freeing excess capacity.
Some implementations do auto-shrink:
A few implementations shrink when the size falls below a threshold (e.g., 25% of capacity). The shrinking factor is typically less aggressive than growth — shrink to 50% capacity rather than shrink to fit. This provides a buffer against thrashing.
For long-lived dynamic arrays that might shrink dramatically, consider periodic explicit compaction. For temporary arrays built up then discarded, the extra capacity doesn't matter. Profile before optimizing — memory overhead from capacity buffers is rarely the bottleneck.
We have explored the internal mechanics of dynamic arrays. Let's consolidate the key insights:
What's next:
We've referenced "amortized O(1)" several times without fully explaining it. The next page provides a rigorous exploration of resizing strategy and amortized cost — the mathematical framework that proves why geometric growth works and what "amortized" really means. This analysis technique applies far beyond dynamic arrays.
You now understand how dynamic arrays achieve automatic resizing while maintaining array performance characteristics. The key insight — that geometric growth amortizes resize costs across many operations — is one of the most important ideas in data structure design. Next, we'll formalize this with proper amortized analysis.