dynamic array
A dynamic array is an array that grows by itself. It keeps a plain array inside (the backing store) plus two numbers: the capacity (how many slots are allocated) and the size (how many you are actually using). While there is room, appending an item just drops it into the next free slot — O(1). C++ std::vector, Java ArrayList and Python's list all work this way.
When the backing array fills up, the dynamic array allocates a bigger one — typically double the capacity — copies the existing items over, and frees the old one. That single append is expensive, O(n), but doubling means it happens rarely: between two costly resizes you get a long run of cheap appends. Averaged out, each append still costs O(1). This averaging is called amortized O(1), and the doubling strategy is the reason it works.
So you keep the array's O(1) indexed access while losing the fixed-size limitation. The trade-offs that remain are the same as a plain array: inserting or deleting in the middle is still O(n) because of shifting, and the capacity can be larger than the size, so a little memory is held in reserve.
#include <vector>
std::vector<int> v; // size 0, capacity 0
for (int i = 0; i < 5; ++i)
v.push_back(i); // amortized O(1) each
// capacity grows like 1 -> 2 -> 4 -> 8 (implementation-defined)
int x = v[3]; // O(1) indexed access
v.insert(v.begin() + 1, 99); // O(n): shifts later elementsMost push_back calls are cheap; the rare doubling-and-copy is spread across them.
Growth by a constant factor (e.g. doubling) gives amortized O(1) append; growing by a fixed +1 each time would make appending O(n) overall.