数组与线性结构
链表
链表把元素分别装在一个个叫节点的小盒子里，散落在内存各处。每个节点存一个值和一个指针（链接），指向下一个节点；最后一个节点指向空。可以想象成寻宝：每条线索只告诉你下一条在哪儿。要找到第五个元素，你得顺着四个链接走过去——没法直接跳。
这种布局把数组的取舍整个反了过来。由于元素并不连续，第 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)。
数组与链表是教科书式的取舍：数组胜在随机访问，链表胜在你已握住位置时的插入/删除。
又称
另见