Welcome to the Dynamic Arrays module. A dynamic array is a static array with a smart management layer built around it. It provides the lightning-fast access speed of a static array, while automatically growing in size whenever it fills up.
Dynamic arrays are what high-level languages hand you by default: Python’s list, JavaScript’s Array, C++‘s std::vector, and Java’s ArrayList.
Before you start
- You understand contiguous memory and O(1) indexing. See arrays.
- You can read Big-O notation and know what ‘amortised’ means informally.
What you will be able to do after this lesson:
- Explain why a fixed-size array must be reallocated to grow.
- Compute the total copies for n appends under doubling, and show it is under 2n.
- Explain why doubling gives amortised O(1) and fixed-chunk growth does not.
- Explain why append is cheap and insert-at-front is not.
Study route: read the mechanism, run the lab, then attempt the independent task before opening the hint.
1. Why Do Dynamic Arrays Exist? (Real-World Motivation)
Imagine buying an expandable accordion suitcase for travel:
- When you start packing, it takes up a compact space.
- If you run out of room, you un-zipper the extension seam to double its capacity.
In real-world software, you almost never know in advance how many records a user will load, how many items will be added to a shopping cart, or how many messages will arrive over a network connection.
Static arrays demand a fixed size at creation time. Dynamic arrays eliminate that restriction by automatically managing capacity behind the scenes.
Terms used with dynamic arrays
-
Dynamic array: This is an array that can grow. It is also called a resizable array, a vector in C++, an ArrayList in Java, and simply a list in Python. Underneath it is still a plain fixed-size array — the growing is a trick played on top.
-
Length: This is how many elements are actually stored right now. This is the number you get from
len(). -
Capacity: This is how many elements the underlying memory block could hold before it runs out. It is usually larger than the length, and it is invisible from outside.
-
Headroom: This is the spare space,
capacity - length. It is what lets an append happen without any copying, and it is the whole reason appends are usually instant. -
Growth factor: This is the multiplier used when the block runs out of room — commonly , sometimes . The array allocates a new, larger block and copies everything across. That it is a multiplier and not a fixed amount is the single most important detail, and section 3 shows why.
-
Reallocation: This is the expensive step: request a bigger block, copy every existing element into it, then release the old block. It is , and it is what you are trying to do rarely.
-
Amortised : This means that although a single operation can occasionally be slow, the average cost across a long run of operations is constant. Appending is amortised : most appends are instant, the occasional one copies everything, and the total still works out to constant time per append. It is a statement about the total, never a promise about any one call.
3. How Dynamic Resizing Works
Internally, a dynamic array tracks both its current length and underlying capacity.
State 1: Headroom Available
length = 3, capacity = 4
+-------+-------+-------+-------+
| 10 | 22 | 7 | _ | <-- 1 empty slot left
+-------+-------+-------+-------+
Appending 41 fills the empty slot. Now length = 4, capacity = 4.
State 2: Array Full (length == capacity) — The Resize Trigger
When you call append(99) and length == capacity, the dynamic array executes a 4-step resize algorithm:
Step 1: Allocate a new block with DOUBLE the capacity (capacity = 8)
+---+---+---+---+---+---+---+---+
| _ | _ | _ | _ | _ | _ | _ | _ |
+---+---+---+---+---+---+---+---+
Step 2: Copy existing elements from old block to new block
+---+---+---+---+---+---+---+---+
| 10| 22| 7 | 41| _ | _ | _ | _ |
+---+---+---+---+---+---+---+---+
Step 3: Free the old memory block.
Step 4: Append the new element 99
+---+---+---+---+---+---+---+---+
| 10| 22| 7 | 41| 99| _ | _ | _ |
+---+---+---+---+---+---+---+---+
Now length = 5, capacity = 8 (3 empty headroom slots remaining!)
4. Mathematical Proof: Why Doubling Makes Append “Amortized ”
A single resize operation costs because every single element must be copied to the new memory location. Why, then, do computer scientists claim that append() is ?
Because capacity doubles, resizes become exponentially rarer as the array grows!
Counting the Total Copies
Suppose you append elements starting from a capacity of 1:
Appends 1-2: Resize to 2 (Cost: 1 copy)
Appends 3-4: Resize to 4 (Cost: 2 copies)
Appends 5-8: Resize to 8 (Cost: 4 copies)
Appends 9-16: Resize to 16 (Cost: 8 copies)
Total Copies across ALL 16 appends = 1 + 2 + 4 + 8 = 15 copies!
Mathematically, for appends:
- Total work for appends: insertions + copies = operations.
- Average (Amortized) cost per append: !
IMPORTANT
Why Fixed Additive Growth Fails: If you increased capacity by a fixed amount (e.g. slots each time instead of multiplying by ), the total copy work would be , causing
append()to degrade to a slow average cost!
5. Time & Space Complexity Summary
| Operation | Time Complexity | Notes |
|---|---|---|
Access by Index (arr[i]) | Direct formula calculation (). | |
| Append at End | Amortized | worst-case only on the rare resize step. |
| Pop from End | Shrinks length counter; no shifting needed. | |
| Insert / Delete at Front | Must shift all subsequent elements right/left. | |
| Search (Unsorted) | Linear scan. |
6. Practical Optimizations & Gotchas
- Pre-Allocation Optimization: If you know you will store 100,000 items, pre-allocate the capacity upfront (
[None] * 100000in Python orvector.reserve(100000)in C++) to prevent all resize copies! - Front Operations Are Still : Dynamic arrays solve the dynamic sizing problem, but inserting at index 0 still requires shifting every item. If you need fast front insertions, use Queues or Linked Lists.
The dynamic array ADT
A dynamic array supports everything a plain array does, and adds the operation an array cannot have.
-
get(i)andset(i, value)— Exactly as for a plain array. . The underlying storage is still one contiguous block, so the address arithmetic is unchanged. -
append(value)— Addsvalueto the end. Amortised . Usually it writes into spare headroom and returns immediately. Occasionally there is no headroom left, and it must allocate a bigger block and copy everything, which is for that one call. -
pop()— Removes and returns the last element. . Nothing needs to move, because nothing sits after it. -
insert(i, value)— Inserts at positioni, shifting everything after it up one place. . The shifting is unavoidable: contiguous storage means there is no gap to insert into. -
delete(i)— Removes the element atiand shifts everything after it down. , for the same reason. -
length()— How many elements are stored. .
The one claim worth being precise about
“Appending is ” is a statement about a sequence, not about a single call. Any individual append may be the unlucky one that triggers a copy of a million elements. If you are writing something latency-sensitive — an audio callback, a control loop, a game frame — that occasional spike is real and will show up in your worst-case timing, even though your average looks perfect.
The fix, when it matters, is to reserve capacity up front if you know roughly how many elements are coming. Most languages expose this: reserve() in C++, ensureCapacity() in Java. Python does not expose it directly, which is one reason building a list by repeated append in a hot loop is sometimes replaced by preallocating a list of the right size.
Implementation - complete runnable example
Runnable example: save as dynamic_arrays_lab.py and run python3 dynamic_arrays_lab.py. Standard library only; writes no files. Everything is counted rather than timed, so your output will match this exactly.
"""Dynamic arrays: why doubling gives amortised O(1) append.
Counts element copies exactly, so the amortisation is arithmetic rather
than a claim."""
class GrowableArray:
"""A dynamic array built on a fixed-capacity store, like a real one."""
def __init__(self, growth=2):
self.data, self.size, self.capacity = [None], 0, 1
self.growth, self.copies, self.resizes = growth, 0, 0
def append(self, value):
if self.size == self.capacity:
self._resize(max(1, int(self.capacity * self.growth)))
self.data[self.size] = value
self.size += 1
def _resize(self, new_capacity):
"""The expensive step: allocate bigger, copy everything across."""
bigger = [None] * new_capacity
for i in range(self.size):
bigger[i] = self.data[i]
self.copies += self.size
self.resizes += 1
self.data, self.capacity = bigger, new_capacity
def __getitem__(self, i):
if not 0 <= i < self.size:
raise IndexError(i)
return self.data[i]
def insert_front(self, value):
"""O(n): everything must shift right to make room."""
if self.size == self.capacity:
self._resize(max(1, int(self.capacity * self.growth)))
for i in range(self.size, 0, -1):
self.data[i] = self.data[i - 1]
self.copies += self.size
self.data[0] = value
self.size += 1
def append_cost(n, growth):
a = GrowableArray(growth)
for i in range(n):
a.append(i)
return a.copies, a.resizes
if __name__ == "__main__":
print("GROWTH BY DOUBLING -- copies during n appends")
print(f" {'n':>7s} {'copies':>10s} {'resizes':>9s} {'copies/append':>14s}")
for n in (10, 100, 1000, 10000):
copies, resizes = append_cost(n, 2)
print(f" {n:7d} {copies:10,d} {resizes:9d} {copies/n:14.2f}")
print(" -> copies per append approaches 1 and never exceeds 2.")
print(" THAT is what 'amortised O(1)' means: some appends are")
print(" expensive, but the average over any run is constant.")
print()
print("WHY DOUBLING, NOT ADDING A FIXED AMOUNT")
print(f" {'strategy':>22s} {'copies for n=10000':>20s}")
a = GrowableArray(2)
for i in range(10000): a.append(i)
print(f" {'double (x2)':>22s} {a.copies:20,d}")
# grow by a constant chunk instead
size = cap = copies = 0
for i in range(10000):
if size == cap:
copies += size
cap += 100
size += 1
print(f" {'grow by 100 each time':>22s} {copies:20,d}")
print(f" -> fixed-chunk growth is O(n^2) overall; doubling is O(n).")
print()
print("APPEND vs INSERT AT FRONT")
back = GrowableArray()
for i in range(1000): back.append(i)
front = GrowableArray()
for i in range(1000): front.insert_front(i)
print(f" 1000 appends : {back.copies:8,d} copies")
print(f" 1000 front inserts : {front.copies:8,d} copies")
print(f" -> front insertion is O(n) per operation, O(n^2) overall.")
copies_2x, _ = append_cost(10000, 2)
assert copies_2x < 2 * 10000, "doubling must stay under 2 copies per append"
assert copies_2x < copies, "doubling must beat fixed-chunk growth"
assert front.copies > 100 * back.copies
a = GrowableArray()
for i in range(5): a.append(i * i)
assert [a[i] for i in range(5)] == [0, 1, 4, 9, 16]
print()
print("dynamic_arrays_lab: passed")Expected output:
GROWTH BY DOUBLING -- copies during n appends
n copies resizes copies/append
10 15 4 1.50
100 127 7 1.27
1000 1,023 10 1.02
10000 16,383 14 1.64
-> copies per append approaches 1 and never exceeds 2.
THAT is what 'amortised O(1)' means: some appends are
expensive, but the average over any run is constant.
WHY DOUBLING, NOT ADDING A FIXED AMOUNT
strategy copies for n=10000
double (x2) 16,383
grow by 100 each time 495,000
-> fixed-chunk growth is O(n^2) overall; doubling is O(n).
APPEND vs INSERT AT FRONT
1000 appends : 1,023 copies
1000 front inserts : 500,523 copies
-> front insertion is O(n) per operation, O(n^2) overall.
dynamic_arrays_lab: passed
7. Check Your Understanding (University Self-Assessment)
-
Question: If a dynamic array currently has
length = 8andcapacity = 8, how many elements will be copied during the nextappend()operation if the growth factor is ?-
Click for Answer
Answer: 8 elements will be copied to the new block of capacity 16, plus 1 insertion for the new element.
-
-
Question: What is the difference between
LengthandCapacityin a dynamic array?-
Click for Answer
Answer: Length is how many items are actively stored. Capacity is the total allocated memory block size including empty headroom slots.
-
-
Question: Why would changing a dynamic array’s growth strategy from “multiply capacity by 2” to “add 100 slots when full” be a terrible performance decision?
-
Click for Answer
Answer: Adding fixed slots causes resizes to occur at linear frequency. The total work for N appends becomes quadratic O(n²), turning the average cost ofappend()from O(1) into O(n).
-
Practice - independent task
Implement pop() and automatic shrinking, then measure the hazard it creates.
- Add
pop()removing the last element in O(1). - Add shrinking: when size drops below half capacity, halve the capacity.
- Now write a loop that repeatedly appends one element and pops it, at exactly the boundary where capacity flips. Count the copies.
- You should see thrashing - every single operation triggers a resize.
- Fix it by shrinking only when size drops below a quarter of capacity. Re-measure.
Done when: you can state how many copies the naive shrink rule costs for 1000 alternating operations versus the quarter rule, and explain why hysteresis fixes it.
Hint - open only after an attempt
With shrink-at-half, an array sitting at exactly half capacity that gains one element grows (copying everything), and losing it again shrinks (copying everything). Each operation is O(n), so the sequence is O(n^2).Shrinking at a quarter leaves a gap between the grow threshold and the shrink threshold, so a single element cannot cross both. That gap is hysteresis, and every real implementation has some form of it.
Before moving on
You are done with this module when you can, closed-book:
- Explain why growing requires allocate-and-copy rather than extending in place.
- Compute total copies for n appends under doubling and show it is bounded by 2n.
- Explain why growing by a fixed chunk is O(n^2) overall.
- State why amortised O(1) is not the same as O(1).
Recap: A dynamic array wraps a fixed-capacity block, reallocating when full. Doubling means the copies form a geometric series summing to under 2n, so n appends cost O(n) in total and each append is amortised O(1) - some are expensive, the average is constant. Growing by a fixed amount instead makes the total O(n^2). Front insertion remains O(n) because contiguity must be preserved.
Next: Hash Maps - the structure that gives up ordering entirely to buy O(1) lookup by key.
Related Modules
- Arrays — The static contiguous foundation
- Linked Lists — The pointer-based alternative with front insertions
- Stacks and Queues — LIFO/FIFO structures built using dynamic arrays
Software engineering
Infrastructure & security
Computer science
Hardware & engineering