FundamentalsFundamentals

Dynamic Array Growth

An array that grows automatically by doubling its capacity, giving amortized O(1) append with O(1) indexed access.

Values to append — Numbers appended one at a time into an empty dynamic array (capacity starts at 1); up to 20

1/38An empty dynamic array. `length` is how many elements exist; `capacity` is how many the allocated buffer can hold. The gap between them is the whole subject.

Element just appendedBeing copied to the new bufferUnused capacityAlready stored

PseudocodeLearn Dynamic Array →

1append(x):
2  if length == capacity:        # buffer is full
3    newCap = capacity * 2       # geometric growth
4    allocate a new buffer of newCap
5    copy all `length` elements across   <- the O(n) step
6    free the old buffer
7  buffer[length] = x
8  length += 1

Variables

length0

capacity1

load0%

reallocs0

totalCopies0

amortized—

Complexity

access O(1)

search O(n)

insert O(n)

delete O(n)

Speed