Dynamic array

A dynamic array is an array-like data structure that grows or shrinks its allocated storage as elements are added or removed, while keeping elements in indexed order.

Amortized analysis: A method for analyzing the average cost per operation across a sequence of operations. It captures why repeated appends are cheap on average despite occasional full-array copies.
std::vector: The resizable contiguous-sequence container in the C++ standard library. It exposes dynamic-array behavior, including indexed access and capacity management.
Linked list: A sequence of nodes connected by references, allowing local insertion without shifting contiguous elements. It contrasts with dynamic arrays in storage layout, indexing cost, and insertion behavior.
Contiguous memory: A region of memory whose addresses occupy an uninterrupted range. Contiguity enables constant-time indexing through address arithmetic.
Time complexity: A measure of how an algorithm’s running time grows with its input size. Dynamic arrays offer constant-time indexing and amortized constant-time appends, but linear-time middle insertions.
Geometric expansion: A resizing strategy that increases capacity by a constant factor when storage fills. Multiplying capacity by a factor limits how often appending requires copying every element.
ArrayList: A resizable-array implementation of the List interface in Java. Its append, indexing, and resizing behavior exemplifies a widely used dynamic array.
Static array: An array with a fixed size established when its storage is allocated. It avoids resizing overhead but cannot accommodate growth beyond its fixed capacity.
Big O notation: A notation describing how an algorithm’s resource use scales with input size. It expresses the growth rates of indexing, appending, and inserting operations.
Space complexity: A measure of how an algorithm’s memory use grows with input size. Unused capacity consumes memory in exchange for fewer reallocations.

Linked from 6 pages