Skip to content

Dynamic Array

A dynamic array is an array that grows. It stores its elements in a fixed-size block of memory and, when that block fills up, allocates a larger one and copies everything across. Python's list, Java's ArrayList and C++'s std::vector are all dynamic arrays.

The guide's implementation is DynamicArray. For the other classic way to store a sequence, and how the two compare, see the singly linked list.

How it works

The array keeps two numbers: its length, the number of elements in use, and its capacity, the number of slots allocated. Appending writes into the next free slot. When the length reaches the capacity there is no free slot, so the array resizes: it allocates a new block, copies every element into it, and carries on.

A single resize costs O(n), because it copies all n elements. What matters is how often that happens, and that is decided by the growth policy: the rule for choosing the new capacity.

Growth policies

Policy New capacity In the library
Doubling twice the current capacity doubling
Geometric the current capacity times a factor above 1 geometric
Additive the current capacity plus a fixed step additive

Doubling is geometric growth with a factor of 2.

Amortized cost of append

With geometric growth, each resize is bigger than the last, but resizes also become rarer at exactly the same rate. Appending n elements copies fewer than 2n elements in total with doubling, so the average cost per append is constant. This is amortized O(1): an individual append is occasionally expensive, but any long run of appends averages out to a constant each.

With additive growth, resizes never become rarer. A step of 16 copies the whole array every 16 appends, forever, which adds up to about n² / 32 copies for n appends. Each append costs O(n) on average.

Measured

The benchmark below appends n integers to an empty array and times the whole run. The first tab divides each time by n, giving the cost of one append: a line that stays flat is constant cost per append, and one that climbs is not. The second tab shows the total time, where the steeper line is the quadratic one. Both axes are logarithmic.

DynamicArray(doubling)DynamicArray(geometric(1.5))DynamicArray(additive(16))list
100 ns1 µs10 µs100 µs1001K10K100K1Mn, the input size (log scale)time per operation (log scale)DynamicArray(doubling), n = 100: 160 nsDynamicArray(doubling), n = 1,000: 150 nsDynamicArray(doubling), n = 10,000: 178 nsDynamicArray(doubling), n = 100,000: 170 nsDynamicArray(doubling), n = 1,000,000: 169 nsDynamicArray(geometric(1.5)), n = 100: 217 nsDynamicArray(geometric(1.5)), n = 1,000: 188 nsDynamicArray(geometric(1.5)), n = 10,000: 214 nsDynamicArray(geometric(1.5)), n = 100,000: 225 nsDynamicArray(geometric(1.5)), n = 1,000,000: 210 nsDynamicArray(additive(16)), n = 1,000: 1.15 µsDynamicArray(additive(16)), n = 2,000: 2.3 µsDynamicArray(additive(16)), n = 5,000: 6.16 µsDynamicArray(additive(16)), n = 10,000: 11.7 µsDynamicArray(additive(16)), n = 20,000: 24.6 µsDynamicArray(additive(16)), n = 50,000: 60.6 µslist, n = 100: 24.4 nslist, n = 1,000: 20.8 nslist, n = 10,000: 21.1 nslist, n = 100,000: 23.6 nslist, n = 1,000,000: 30.8 ns

n DynamicArray(doubling) DynamicArray(geometric(1.5)) DynamicArray(additive(16)) list
100 160 ns 217 ns 24.4 ns
1,000 150 ns 188 ns 1.15 µs 20.8 ns
2,000 2.3 µs
5,000 6.16 µs
10,000 178 ns 214 ns 11.7 µs 21.1 ns
20,000 24.6 µs
50,000 60.6 µs
100,000 170 ns 225 ns 23.6 ns
1,000,000 169 ns 210 ns 30.8 ns

DynamicArray(doubling)DynamicArray(geometric(1.5))DynamicArray(additive(16))list
10 µs100 µs1 ms10 ms100 ms1 s1001K10K100K1Mn, the input size (log scale)total time (log scale)DynamicArray(doubling), n = 100: 16 µsDynamicArray(doubling), n = 1,000: 150 µsDynamicArray(doubling), n = 10,000: 1.78 msDynamicArray(doubling), n = 100,000: 17 msDynamicArray(doubling), n = 1,000,000: 169 msDynamicArray(geometric(1.5)), n = 100: 21.7 µsDynamicArray(geometric(1.5)), n = 1,000: 188 µsDynamicArray(geometric(1.5)), n = 10,000: 2.14 msDynamicArray(geometric(1.5)), n = 100,000: 22.5 msDynamicArray(geometric(1.5)), n = 1,000,000: 210 msDynamicArray(additive(16)), n = 1,000: 1.15 msDynamicArray(additive(16)), n = 2,000: 4.61 msDynamicArray(additive(16)), n = 5,000: 30.8 msDynamicArray(additive(16)), n = 10,000: 117 msDynamicArray(additive(16)), n = 20,000: 493 msDynamicArray(additive(16)), n = 50,000: 3.03 slist, n = 100: 2.44 µslist, n = 1,000: 20.8 µslist, n = 10,000: 211 µslist, n = 100,000: 2.36 mslist, n = 1,000,000: 30.8 ms

n DynamicArray(doubling) DynamicArray(geometric(1.5)) DynamicArray(additive(16)) list
100 16 µs 21.7 µs 2.44 µs
1,000 150 µs 188 µs 1.15 ms 20.8 µs
2,000 4.61 ms
5,000 30.8 ms
10,000 1.78 ms 2.14 ms 117 ms 211 µs
20,000 493 ms
50,000 3.03 s
100,000 17 ms 22.5 ms 2.36 ms
1,000,000 169 ms 210 ms 30.8 ms
slope 1.01 1.00 2.02 1.03

Measured on cs-survival-kit 0.6.0 · CPython 3.13.16 · Linux x86_64 · 2026-10-05. Each time is the best of five runs. The slope is fitted on a log-log scale: about 1 is linear, about 2 is quadratic. Both chart axes are logarithmic, so a power law is a straight line and its steepness is that slope.

Both geometric policies stay flat as n grows by four orders of magnitude, just like the built-in list. The additive column grows in step with n. list is faster throughout because it is implemented in C; what the two share is the shape of the curve.

Choosing a factor

Any factor above 1 gives amortized O(1) appends. The factor trades time for memory: a larger one resizes less often, but leaves more of the capacity unused straight after a resize.

geometric(1.25)geometric(1.5)geometric(2.0)geometric(3.0)
100 ns200 ns500 ns1001K10K100K1Mn, the input size (log scale)time per operation (log scale)geometric(1.25), n = 100: 302 nsgeometric(1.25), n = 1,000: 266 nsgeometric(1.25), n = 10,000: 284 nsgeometric(1.25), n = 100,000: 303 nsgeometric(1.25), n = 1,000,000: 301 nsgeometric(1.5), n = 100: 217 nsgeometric(1.5), n = 1,000: 189 nsgeometric(1.5), n = 10,000: 219 nsgeometric(1.5), n = 100,000: 225 nsgeometric(1.5), n = 1,000,000: 209 nsgeometric(2.0), n = 100: 167 nsgeometric(2.0), n = 1,000: 151 nsgeometric(2.0), n = 10,000: 178 nsgeometric(2.0), n = 100,000: 171 nsgeometric(2.0), n = 1,000,000: 169 nsgeometric(3.0), n = 100: 140 nsgeometric(3.0), n = 1,000: 165 nsgeometric(3.0), n = 10,000: 179 nsgeometric(3.0), n = 100,000: 166 nsgeometric(3.0), n = 1,000,000: 171 ns

n geometric(1.25) geometric(1.5) geometric(2.0) geometric(3.0)
100 302 ns 217 ns 167 ns 140 ns
1,000 266 ns 189 ns 151 ns 165 ns
10,000 284 ns 219 ns 178 ns 179 ns
100,000 303 ns 225 ns 171 ns 166 ns
1,000,000 301 ns 209 ns 169 ns 171 ns

geometric(1.25)geometric(1.5)geometric(2.0)geometric(3.0)
10 µs100 µs1 ms10 ms100 ms1001K10K100K1Mn, the input size (log scale)total time (log scale)geometric(1.25), n = 100: 30.2 µsgeometric(1.25), n = 1,000: 266 µsgeometric(1.25), n = 10,000: 2.84 msgeometric(1.25), n = 100,000: 30.3 msgeometric(1.25), n = 1,000,000: 301 msgeometric(1.5), n = 100: 21.7 µsgeometric(1.5), n = 1,000: 189 µsgeometric(1.5), n = 10,000: 2.19 msgeometric(1.5), n = 100,000: 22.5 msgeometric(1.5), n = 1,000,000: 209 msgeometric(2.0), n = 100: 16.7 µsgeometric(2.0), n = 1,000: 151 µsgeometric(2.0), n = 10,000: 1.78 msgeometric(2.0), n = 100,000: 17.1 msgeometric(2.0), n = 1,000,000: 169 msgeometric(3.0), n = 100: 14 µsgeometric(3.0), n = 1,000: 165 µsgeometric(3.0), n = 10,000: 1.79 msgeometric(3.0), n = 100,000: 16.6 msgeometric(3.0), n = 1,000,000: 171 ms

n geometric(1.25) geometric(1.5) geometric(2.0) geometric(3.0)
100 30.2 µs 21.7 µs 16.7 µs 14 µs
1,000 266 µs 189 µs 151 µs 165 µs
10,000 2.84 ms 2.19 ms 1.78 ms 1.79 ms
100,000 30.3 ms 22.5 ms 17.1 ms 16.6 ms
1,000,000 301 ms 209 ms 169 ms 171 ms
slope 1.01 1.00 1.01 1.02

Measured on cs-survival-kit 0.6.0 · CPython 3.13.16 · Linux x86_64 · 2026-10-05. Each time is the best of five runs. The slope is fitted on a log-log scale: about 1 is linear, about 2 is quadratic. Both chart axes are logarithmic, so a power law is a straight line and its steepness is that slope.

A larger step does not fix additive growth

It is tempting to think a big enough step makes additive growth acceptable. A larger step does start out cheap, but the cost per append still rises with n. It delays the quadratic behaviour without removing it.

additive(16)additive(256)additive(4096)doubling
100 ns1 µs10 µs100 µs1K10K100K1Mn, the input size (log scale)time per operation (log scale)additive(16), n = 1,000: 1.15 µsadditive(16), n = 2,000: 2.37 µsadditive(16), n = 5,000: 6.1 µsadditive(16), n = 10,000: 11.8 µsadditive(16), n = 20,000: 24.9 µsadditive(16), n = 50,000: 61.6 µsadditive(256), n = 5,000: 495 nsadditive(256), n = 10,000: 864 nsadditive(256), n = 20,000: 1.62 µsadditive(256), n = 50,000: 3.86 µsadditive(256), n = 100,000: 7.58 µsadditive(256), n = 200,000: 15 µsadditive(4096), n = 50,000: 362 nsadditive(4096), n = 100,000: 618 nsadditive(4096), n = 200,000: 1.05 µsadditive(4096), n = 500,000: 2.45 µsadditive(4096), n = 1,000,000: 4.84 µsdoubling, n = 1,000: 153 nsdoubling, n = 10,000: 186 nsdoubling, n = 100,000: 171 nsdoubling, n = 1,000,000: 169 ns

n additive(16) additive(256) additive(4096) doubling
1,000 1.15 µs 153 ns
2,000 2.37 µs
5,000 6.1 µs 495 ns
10,000 11.8 µs 864 ns 186 ns
20,000 24.9 µs 1.62 µs
50,000 61.6 µs 3.86 µs 362 ns
100,000 7.58 µs 618 ns 171 ns
200,000 15 µs 1.05 µs
500,000 2.45 µs
1,000,000 4.84 µs 169 ns

additive(16)additive(256)additive(4096)doubling
100 µs1 ms10 ms100 ms1 s1K10K100K1Mn, the input size (log scale)total time (log scale)additive(16), n = 1,000: 1.15 msadditive(16), n = 2,000: 4.74 msadditive(16), n = 5,000: 30.5 msadditive(16), n = 10,000: 118 msadditive(16), n = 20,000: 499 msadditive(16), n = 50,000: 3.08 sadditive(256), n = 5,000: 2.48 msadditive(256), n = 10,000: 8.64 msadditive(256), n = 20,000: 32.4 msadditive(256), n = 50,000: 193 msadditive(256), n = 100,000: 758 msadditive(256), n = 200,000: 3 sadditive(4096), n = 50,000: 18.1 msadditive(4096), n = 100,000: 61.8 msadditive(4096), n = 200,000: 209 msadditive(4096), n = 500,000: 1.23 sadditive(4096), n = 1,000,000: 4.84 sdoubling, n = 1,000: 153 µsdoubling, n = 10,000: 1.86 msdoubling, n = 100,000: 17.1 msdoubling, n = 1,000,000: 169 ms

n additive(16) additive(256) additive(4096) doubling
1,000 1.15 ms 153 µs
2,000 4.74 ms
5,000 30.5 ms 2.48 ms
10,000 118 ms 8.64 ms 1.86 ms
20,000 499 ms 32.4 ms
50,000 3.08 s 193 ms 18.1 ms
100,000 758 ms 61.8 ms 17.1 ms
200,000 3 s 209 ms
500,000 1.23 s
1,000,000 4.84 s 169 ms
slope 2.02 1.93 1.87 1.01

Measured on cs-survival-kit 0.6.0 · CPython 3.13.16 · Linux x86_64 · 2026-10-05. Each time is the best of five runs. The slope is fitted on a log-log scale: about 1 is linear, about 2 is quadratic. Both chart axes are logarithmic, so a power law is a straight line and its steepness is that slope.

Complexity

Operation Time Notes
Read or write by index O(1)
Append O(1) amortized O(n) for the append that triggers a resize
Pop from the end O(1)
Iterate O(n)

These assume a geometric growth policy.