陣列與線性結構
鏈結串列
鏈結串列把元素分別裝在一個個叫節點的小盒子裡，散落在記憶體各處。每個節點存一個值和一個指標（鏈結），指向下一個節點；最後一個節點指向空。可以想成尋寶：每條線索只告訴你下一條在哪裡。要找到第五個元素，你得順著四個鏈結走過去——沒法直接跳。
這種佈局把陣列的取捨整個反了過來。由於元素並不連續，第 i 個元素沒有現成的計算公式，所以定位到第 i 位或搜尋某個值都是 O(n)——你得沿著鏈子走。但如果你手裡已經握著某個節點，把新節點接進去或把一個節點摘出來只是幾次指標重連：在已知位置插入/刪除是 O(1)，不必搬移任何元素。在頭部插入正是經典的 O(1) 操作。
單向鏈結串列只向前鏈結；雙向鏈結串列還保存一個 prev 指標，於是你能雙向行走，並在僅給出某節點時以 O(1) 刪除它。代價是每個元素多花的記憶體（那些指標），以及糟糕的快取表現——因為順鏈跳轉會在記憶體裡東奔西跑，而不是在一整塊裡整齊前進。
struct Node { int v; Node* next; };
// head -> [10|*] -> [20|*] -> [30|/] (/ = nullptr)
Node* push_front(Node* head, int x) {
Node* n = new Node{x, head}; // point new node at old head
return n; // O(1): no shifting
}
int nth(Node* head, int i) { // O(n): must walk the chain
while (i-- && head) head = head->next;
return head ? head->v : -1;
}在頭部插入是 O(1)；尋找第 i 個值是 O(n)。
陣列與鏈結串列是教科書式的取捨：陣列勝在隨機存取，鏈結串列勝在你已握住位置時的插入/刪除。
又稱
另見