Section 4: Dynamic Arrays — Structure and Behavior (37–48)

Underlying storage mechanism of a dynamic array

A backing array

Dynamic array size

The number of elements currently stored

Dynamic array capacity

The number of elements the backing array can hold before needing to resize

Relationship between dynamic array size and capacity

They can differ because capacity can exceed size

Dynamic array resizing trigger

Attempting to add an element when the backing array is completely full

Common growth strategy for dynamic array capacity

Doubling the existing capacity

Reason elements are copied during dynamic array resizing

To transfer all existing elements from the old backing array into the new, larger backing array

Dynamic-array constructor

Initializes the data structure and establishes its initial state, including its size and capacity

Class invariant

A condition or rule that must always hold true for an object's state to be considered valid

Purpose of checking class invariants after an operation

To verify that the operation maintained internal rules and left the data structure in a valid state

Amortized analysis

An evaluation technique that determines the average cost per operation over a sequence of operations

Reason dynamic array addition achieves amortized efficiency

Expensive resizing operations occur infrequently, allowing their high cost to be distributed across many constant-time additions