陣列與線性結構
動態陣列
動態陣列是一種會自己長大的陣列。它內部藏著一個普通陣列（底層儲存），再加兩個數字：容量（已配置多少個槽位）與大小（實際用了多少個）。只要還有空位，追加元素就是把它放進下一個空槽——O(1)。C++ 的 std::vector、Java 的 ArrayList、Python 的 list 都是這樣運作的。
當底層陣列裝滿時，動態陣列會配置一個更大的（通常是容量翻倍），把既有元素全部複製過去，再釋放舊的。這一次追加很貴，是 O(n)，但翻倍意味著它很少發生：兩次昂貴擴充之間，是一長串廉價的追加。攤平下來，每次追加仍然是 O(1)。這種平均叫做攤還 O(1)，而翻倍策略正是它成立的原因。
於是你保留了陣列的 O(1) 索引存取，又擺脫了定長的限制。剩下的取捨與普通陣列相同：在中間插入或刪除仍然是 O(n)（要搬移元素），而且容量可能大於實際大小，所以會預留一點記憶體。
#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 elements大多數 push_back 都很便宜；偶發的翻倍複製被分攤到它們之中。
按常數倍數增長（如翻倍）才能得到攤還 O(1) 的追加；若每次只 +1 地擴充，整體追加會退化成 O(n)。
又稱
另見