Dynamic Arrays

The previous lesson established that an array is a fixed-size contiguous block, and that this block cannot be grown afterward. When the number of elements is not known in advance, this constraint is binding.

The solution is not to eliminate the constraint but to live with it: when the array fills up, a new, larger array is allocated, the old elements are copied into it, and the old block is released. This structure is called a dynamic array.

Capacity and Length

A dynamic array holds two numbers:

• Length: The actual number of elements it contains.
• Capacity: The maximum number of elements the allocated block can hold.

Capacity is always equal to or greater than length. The difference between them is space that is allocated but not yet used; appending is cheap as long as it uses this room.

When length reaches capacity, reallocation is required: a new and larger block is allocated, and all elements are copied. Copying is proportional to the number of elements — that is, $O(n)$.

The Growth Factor

The critical question is: how large should the new capacity be?

Growing by a fixed amount — adding a constant number to capacity each time — is a poor choice. If capacity increased one at a time, the total copying done to insert $n$ elements would be:

$$1 + 2 + 3 + \dots + (n-1) = \frac{n(n-1)}{2}$$

This means $O(n^2)$: inserting a thousand elements does approximately half a million copies.

Growing by doubling — multiplying capacity by a factor (commonly two) each time — changes the total cost fundamentally. If capacity starts at $1$ and doubles, the total of the copies made until $n$ elements are reached is:

$$1 + 2 + 4 + \dots + \frac{n}{2} < n$$

The geometric sum itself is less than twice the last term. So the total number of copies for $n$ insertions is less than $n$; the average cost per insertion is constant.

Amortized Cost

This observation calls for a concept. Looked at individually, most append operations are $O(1)$, some are $O(n)$; the worst-case cost is linear.

But expensive operations are rare, and because capacity doubles after every expensive operation, twice as many cheap operations happen before the next expensive one. The value obtained by dividing the total cost of a sequence of operations by the number of operations is called the amortized cost.

In a dynamic array, the amortized cost of appending is $O(1)$. This does not mean “every append takes constant time”; it means “$n$ appends together take $O(n)$.” The distinction matters in latency-sensitive systems: it must be known that any single append can take a long time.

class DynamicArray:
    """An array that grows by doubling its capacity."""

    def __init__(self) -> None:
        self._block: list = [None]     # capacity starts at 1
        self._length = 0
        self.copies = 0                # counter for measurement

    def __len__(self) -> int:
        return self._length

    def capacity(self) -> int:
        return len(self._block)

    def append(self, value: int) -> None:
        if self._length == self.capacity():
            self._grow()
        self._block[self._length] = value
        self._length += 1

    def _grow(self) -> None:
        new_block = [None] * (self.capacity() * 2)
        for i in range(self._length):          # each element is moved to the new block
            new_block[i] = self._block[i]
            self.copies += 1
        self._block = new_block

    def __getitem__(self, i: int) -> int:
        if not 0 <= i < self._length:
            raise IndexError("index out of range")
        return self._block[i]


array = DynamicArray()
for value in range(16):
    array.append(value)

print(len(array), array.capacity())    # 16 16
print(array.copies)                    # 15    — total copies, fewer than the element count
print(array[3])                        # 3

The number of copies made for sixteen appends is $1 + 2 + 4 + 8 = 15$. That is less than one copy per append on average; the bound given by the geometric sum is confirmed by the count.

This count is the simplest form of amortized analysis: alongside its own cost, every append sets aside a share for future copying; when reallocation comes, these accumulated shares cover the cost.

The factor does not have to be two. A smaller factor (for example, $1.5$) leaves less empty room but copies more often; a larger factor does the opposite. In both cases the amortized cost stays constant — what changes is the size of the constant factor.

Preallocation

If the number of elements is known in advance, growth may never happen at all. Most dynamic array implementations offer an operation that lets capacity be set up front.

The gain is twofold. Reallocation and copying disappear entirely; and because the allocated block is a single piece, memory fragmentation is reduced. If it is known that a result of a thousand elements will be produced, giving capacity a thousand up front prevents ten reallocations.

result = []
# When capacity is known up front, the language's preallocation facility is used.
# Without preallocation, producing the result directly at its target size does the same job:
ready = [0] * 1000                      # a single allocation, no copying
for i in range(1000):
    ready[i] = i * 3
print(len(ready), ready[999])           # 1000 2997

This is not premature optimization: when the final size is known, preallocation also improves the code’s readability — the intent is written explicitly.

Shrinking and Oscillation

When elements are removed, capacity is expected to shrink as well; otherwise an array that has once grown never releases memory.

The shrink threshold must be chosen with care. If capacity is halved as soon as length drops to half of capacity, oscillation results: with the array right at that boundary, an append followed by a delete, repeated, triggers reallocation every single time. Every operation becomes $O(n)$ and the amortized gain disappears.

The standard solution is to separate the thresholds: capacity doubles when it fills up, but is halved only when length drops to one quarter of capacity. The gap between the two prevents operations that go back and forth near the boundary from triggering reallocation.

The Counterpart in Real Languages

Most languages’ standard “list” or “vector” structure is a dynamic array. Appending at the end is amortized constant, inserting at the start is linear; this asymmetry determines which end is used when writing code.

One detail is what is actually stored. Fixed-width types can be kept directly in the block; when object references are stored instead, the block carries pointers and the real values sit scattered on the heap. The second arrangement offers flexibility and lowers cache compatibility. The contiguous layout discussion in the How Computers Work course covered this distinction.

Cost Table

Structure	Access	Search	Insert at start	Insert at end	Delete from middle
Array (fixed size)	$O(1)$	$O(n)$	$O(n)$	$O(1)$*	$O(n)$
Dynamic array	$O(1)$	$O(n)$	$O(n)$	$O(1)$ amortized	$O(n)$

* As long as room remains.

Summary

• A dynamic array overcomes the fixed-size constraint by allocating a larger block and copying elements over when it fills up.
• Capacity denotes allocated room; length denotes the actual number of elements.
• Growing by a fixed amount makes the total cost $O(n^2)$; under doubling growth, the total copying is less than $n$.
• Amortized cost is the total cost of a sequence of operations divided by the number of operations; the amortized cost of appending is constant, though the cost of any single append is not.
• The shrink threshold is chosen separately from the growth threshold; otherwise operations at the boundary produce oscillation.

Next Step

The dynamic array made appending cheap, but inserting at the start or middle is still linear. The source of the shifting cost was contiguous layout. The next lesson takes up a structure that abandons contiguity entirely — the linked list — and what this trade-off gains and loses.