回到最底层：每个结构在栈/堆上长什么样，指针怎么串起来（见 C 指针第 1、2、9 章）。
typedef struct { int *data; int len, cap; } SeqList;
SeqList 本身若定义在函数里是栈上的结构体（约 12 字节），但它的 data 指向 malloc 来的堆块。a[i] 编译成 *(data + i)——基址 + 偏移，一次地址计算 + 一次解引用（C 指针第 4 章）。
栈 堆
┌────────────┐ ┌──────────────────────┐
│ data ──────┼──────►│ 0 │ 1 │ 2 │ ... │n-1│ ← 连续 int
│ len cap │ └──────────────────────┘
└────────────┘
typedef struct Node { int val; struct Node *next; } Node;
每个 Node 各自 malloc，地址无规律地散布在堆里，next 存下一个节点的地址。
栈 堆
┌──────┐ ┌──────┬───┐ ┌──────┬───┐ ┌──────┬────┐
│ head─┼─►│ val1 │ ──┼──►│ val2 │ ──┼──►│ val3 │NULL│
└──────┘ └──────┴───┘ └──────┴───┘ └──────┴────┘
地址A 地址B(≠A+16) 地址C
head->next->val 是两次解引用：先顺着 next 拿到 B，再读 B 的 val。树、图、跳表、Trie 都是这个模型的推广——多几个指针字段而已（第 5、6、11 章）。
| 内存 | 分配方式 | 生命周期 | 适合放 |
|---|---|---|---|
| 栈 | 编译器自动 | 函数返回即失效 | 局部变量、小数组 |
| 堆 | malloc/free | 手动控制 | 链表节点、树节点、动态数组 |
关键推论：链表节点必须放堆（函数返回后仍存活）；放栈的局部节点返回即悬空——「返回局部变量地址」是经典陷阱（见 C 指针第 2 章）。
CPU 从内存读数据以**缓存行（cache line，64 字节）**为单位。顺序表元素连续，读 a[i] 时把邻居一起搬进缓存，下次访问 a[i+1] 命中；链表节点离散，每次跳 next 大概率缓存未命中（cache miss），要重新访内存，慢一个数量级。
// 同样遍历 n 个元素：数组远快于链表（缓存局部性）
for (int i = 0; i < n; i++) sum += arr[i]; // 顺序访问，缓存命中率高
for (Node *p = head; p; p = p->next) sum += p->val; // 随机跳转，频繁 miss
| 结构 | 每元素额外开销 | 来源 |
|---|---|---|
| 顺序表 | 0（或预留 cap 浪费） | 纯数据 |
| 单链表 | 8 字节 | 一个 next 指针 |
| 双向链表 | 16 字节 | prev + next |
| 二叉树 | 16 字节 | left + right |
| 哈希表（链地址） | 桶数组 + 节点指针 | 桶 + next |
| Trie | 每字符一个指针数组 | 26 或 256 个指针 |
| 跳表 | 多层 next 指针 | 期望 2×指针 |
printf("%zu %zu\n", sizeof(int), sizeof(Node)); // 8 vs 16：一个指针就翻倍
对比：数组连续、顺序访问命中缓存；链表离散、指针跳转打破局部性。故大量数据下数组遍历/排序常反超链表。
对比：顺序表近零开销但需连续块；链表/树付指针税换灵活性；Trie、跳表多指针换速度（空间换时间）。
第 1 章只数操作次数，本章补上每次操作的常数代价（一次解引用、一次 cache miss、一次 malloc）。数据结构 = 内存布局 + 指针关系 + 操作算法。