链表、队列、栈与线性结构
#数据结构 · #链表 · #队列 · #栈 · #线性表 · #数组
线性数据结构是最基础也是最广泛使用的结构。本文覆盖：单向链表、双向链表、动态数组(Slice/Vector)、队列、优先队列、栈，以及 Redis 中的特殊紧凑结构 ziplist/listpack。
1. 单向链表（Singly Linked List）
1.1 结构与特点
Head → [data|next] → [data|next] → [data|next] → NULL| 操作 | 复杂度 | 说明 |
|---|---|---|
| 在头部插入 | O(1) | 修改 head 指针即可 |
| 在尾部插入 | O(n) 或 O(1) | 无 tail 指针需遍历；有 tail 指针 O(1) |
| 按位置查找 | O(n) | 必须从 head 开始遍历 |
| 删除节点 | O(n) | 需要找到前驱节点 |
| 在已知节点后插入 | O(1) | 只需修改 next 指针 |
1.2 经典实现
c
typedef struct Node {
int data;
struct Node *next;
} Node;
// 头部插入 O(1)
void push_front(Node **head, int val) {
Node *n = malloc(sizeof(Node));
n->data = val;
n->next = *head;
*head = n;
}
// 反转链表（三指针法）O(n)
Node *reverse(Node *head) {
Node *prev = NULL, *curr = head, *next;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}mermaid
flowchart LR
subgraph Before["反转前"]
H1((Head)) --> N1["1"] --> N2["2"] --> N3["3"] --> N4["4"] --> NULL1((NULL))
end
subgraph After["反转后"]
H2((Head)) --> M1["4"] --> M2["3"] --> M3["2"] --> M4["1"] --> NULL2((NULL))
end
Before -.->|"prev → curr → next<br/>三指针 O(n)"| After
style H1 fill:#F44336,color:#fff
style H2 fill:#4CAF50,color:#fff1.3 适用算法
- 链地址法哈希表：每个 bucket 是一个链表
- LRU Cache：链表 + HashMap 实现 O(1) get/put
- 图的邻接表：每个顶点的边用链表存储
- 内存分配器的空闲链表：malloc 的 free list 是链表
2. 双向链表（Doubly Linked List）
2.1 结构
NULL ← [prev|data|next] ↔ [prev|data|next] ↔ [prev|data|next] → NULL相比单向链表的优势：可以在 O(1) 时间删除任意节点（只要有该节点的指针），因为可以直接访问前驱。
2.2 经典应用
go
// Go 标准库 container/list 基于双向链表
import "container/list"
l := list.New()
l.PushBack("world")
l.PushFront("hello")
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}2.3 Linux 内核的双向链表
Linux 内核使用了一种精妙的侵入式链表设计——链表节点嵌入在宿主结构体中：
c
// include/linux/list.h（简化）
struct list_head {
struct list_head *next, *prev;
};
struct my_struct {
int data;
struct list_head list; // 嵌入的链表节点
};
// 通过 list_head 反推宿主结构体指针
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
// container_of 原理: (type *)((char *)ptr - offsetof(type, member))优势：一个结构体可以同时挂在多个链表上，无需额外分配链表节点内存。
2.4 适用算法
- LRU / LFU：需要频繁移动节点到头部/尾部
- Redis 的 quicklist：由多个 ziplist 节点组成的双向链表
- 操作系统就绪队列：调度器维护的可运行进程链表
3. Slice（Go）与 Vector（C++/Rust）
3.1 动态数组 = 连续内存 + 自动扩容
ptr → [elem0][elem1][elem2][elem3][____][____][____][____]
←———— len=4 ————→ ←———— cap=8 ——————————————→| 语言 | 类型 | 扩容策略 |
|---|---|---|
| Go | []T slice | <1024 → 翻倍；≥1024 → 1.25× |
| C++ | std::vector | MSVC 1.5×；GCC/libc++ 2× |
| Rust | Vec<T> | 翻倍（2 * self.cap） |
| Java | ArrayList | new = old + old/2（1.5×） |
| Python | list | 大约 new = old + (old >> 3) + 3（约 1.125×） |
3.2 Go Slice 底层
go
type slice struct {
array unsafe.Pointer // 指向底层数组
len int // 当前长度
cap int // 容量
}
// append 扩容示意
s := make([]int, 0, 2)
s = append(s, 1) // len=1 cap=2
s = append(s, 2) // len=2 cap=2
s = append(s, 3) // len=3 cap=4（触发扩容，迁移数据）3.3 切片操作的时间陷阱
go
// 陷阱1: 切片共享底层数组
a := []int{1, 2, 3, 4}
b := a[1:3] // b = [2, 3], cap=3（共享 a 的底层数组）
b = append(b, 99) // b=[2,3,99], 但 a 也变成了 [1,2,3,99]！
// 解决办法: b := a[1:3:3]（限制 cap=2）
// 陷阱2: range 中的值拷贝
for _, v := range items {
go func(val Item) { process(val) }(v) // OK: v 是拷贝
}4. 栈（Stack）— LIFO
Push → [3] Pop → 3
[2] [2]
[1] [1]| 操作 | 复杂度 |
|---|---|
| Push | O(1) |
| Pop | O(1) |
| Peek | O(1) |
4.1 应用场景
- 函数调用栈：每个栈帧保存返回地址、局部变量
- 表达式求值：中缀→后缀，括号匹配
- DFS 非递归实现：显式用栈替代递归
- 撤销操作：编辑器 Undo/Redo
- 浏览器的前进后退
4.2 单调栈 — 进阶技巧
go
// 找数组中每个元素的下一个更大元素（Next Greater Element）
func nextGreater(nums []int) []int {
res := make([]int, len(nums))
stack := []int{} // 存下标，栈内值单调递减
for i, v := range nums {
for len(stack) > 0 && nums[stack[len(stack)-1]] < v {
top := stack[len(stack)-1]
res[top] = v
stack = stack[:len(stack)-1]
}
stack = append(stack, i)
}
return res
}
// 时间复杂度 O(n)，每个元素入栈出栈各一次5. 队列（Queue）— FIFO
Enqueue → [3][2][1] → Dequeue| 操作 | 链表实现 | 数组（环形缓冲区） |
|---|---|---|
| Enqueue | O(1) | O(1)（均摊） |
| Dequeue | O(1) | O(1) |
| Peek | O(1) | O(1) |
5.1 环形缓冲区（Ring Buffer）
go
// 固定大小的环形队列 — Go channel 的底层结构
type RingBuf struct {
buf []int
head int // 读指针
tail int // 写指针
size int
}
func (r *RingBuf) Enqueue(v int) bool {
if r.size == len(r.buf) { return false }
r.buf[r.tail] = v
r.tail = (r.tail + 1) % len(r.buf)
r.size++
return true
}环形缓冲区的关键优势：无需移动数据，读写各维护一个指针循环移动。
5.2 应用场景
- 消息队列：生产者-消费者模型
- BFS：广度优先搜索的标准实现
- 线程池任务队列：
sync.Pool的本地队列 - 网络数据包缓冲：网卡驱动中的 ring buffer
- 滑动窗口：TCP 的发送/接收窗口
6. 优先队列（Priority Queue）— 按优先级出队
| 实现方式 | Enqueue | Dequeue（取最值） |
|---|---|---|
| 无序数组 | O(1) | O(n) |
| 有序数组 | O(n) | O(1) |
| 二叉堆 | O(log n) | O(log n) |
| 斐波那契堆 | O(1) | O(log n) 均摊 |
6.1 Go 的堆实现
go
import "container/heap"
type Item struct {
value string
priority int
index int // heap.Interface 要求维护
}
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].priority < pq[j].priority } // 小顶堆
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i]; pq[i].index = i; pq[j].index = j }
func (pq *PriorityQueue) Push(x any) { *pq = append(*pq, x.(*Item)) }
func (pq *PriorityQueue) Pop() any { old := *pq; n := len(old); x := old[n-1]; *pq = old[:n-1]; return x }6.2 应用场景
- Dijkstra 最短路径：每次取距离最小的顶点
- Top K 问题：用小顶堆维护最大的 K 个元素
- 定时器管理：Linux 内核用红黑树，Go runtime 用四叉堆
- Huffman 编码：每次取频率最小的两个节点合并
6.3 各语言定时器的堆设计
| 运行时 | 数据结构 | 为何 |
|---|---|---|
| Go (≥1.14) | 四叉堆 | 缓存局部性更好，每层 4 个节点 → 更浅 |
| Linux 内核 | 红黑树 | 需要 O(log n) 的删除任意节点 |
| libevent | 最小堆 | 简单高效 |
| nginx | 红黑树 | 同 Linux 内核 |
7. 双向队列（Deque）— 两端操作
PushFront → [3][2][1] ← PushBack
PopFront ← [3][2][1] → PopBackGo 中没有内置 Deque，但可以用 list.List 或自己实现环形缓冲区。
8. Redis 紧凑结构：ziplist 与 listpack
传统链表每个节点有独立内存分配和前后指针，内存开销大（指针 8B×2 + 对象头 ≥ 24B per node）。对于小型集合（几个到几百个元素），Redis 使用连续内存的紧凑编码，大幅节约内存。
8.1 为什么要紧凑编码？
传统链表 (adlist):
┌───┬───┬───┐ ┌───┬───┬───┐ ┌───┬───┬───┐
│prev│next│val│→ │prev│next│val│→ │prev│next│val│→
└───┴───┴───┘ └───┴───┴───┘ └───┴───┴───┘
malloc + malloc + malloc
每个节点: 16B(指针) + 8B(val指针) + 16B(malloc头) ≈ 40B
ziplist (紧凑):
┌─────────┬───────────────────────────────────┐
│ zlbytes │ entry1│entry2│ ... │entryN│ zlend │
└─────────┴───────────────────────────────────┘
一次 malloc，所有数据紧凑排列
每个 entry: 1-5B(prevlen) + 1-5B(encoding) + data| 场景 | 传统链表 | ziplist |
|---|---|---|
| 存储 3 个 "hello"(5B) | ~120B + 3×5B = 135B | ~3×(1+1+5) +10B ≈ 32B |
| 内存效率 | ~22% | ~88% |
| 查找第 k 个 | O(n) 遍历指针 | O(n) 顺序扫描（但连续内存缓存友好） |
8.2 ziplist — 完整结构解析
┌────────┬────────┬────────┬──────────────┬───────────┬──────┐
│zlbytes │zltail │zllen │ entry1 │ entry2... │zlend │
│ 4B │ 4B │ 2B │ 变长 │ 变长 │ 1B │
│总字节数│尾偏移 │元素数 │ prevlen+enc+data │ │ 0xFF │
└────────┴────────┴────────┴──────────────┴───────────┴──────┘Entry 内部编码（核心难点）：
entry = <prevlen> <encoding> <entry-data>
prevlen: 前一个 entry 的长度（用于反向遍历 zlend→zltail→...）
├─ 如果前驱长度 < 254B → 1 字节
└─ 如果前驱长度 ≥ 254B → 5 字节 (0xFE + 4B长度)
encoding: 编码当前 entry 的数据类型和长度
├─ 00pppppp: 6位长度, 字符串 ≤ 63B
├─ 01pppppp|qqqqqqqq: 14位长度, 字符串 ≤ 16383B
├─ 10000000|qqqqqqqq|rrrrrrrr|ssssssss|tttttttt: 32位长度, 字符串 >16383B
├─ 11000000: int16_t
├─ 11010000: int32_t
├─ 11100000: int64_t
└─ 1111xxxx: 0-12 的小整数 (xxxx=0001 表示 1)go
// 用 Go 演示 entry 的编码过程
func encodeEntry(prevLen, data []byte) []byte {
entry := make([]byte, 0)
// 1. 编码 prevlen
if len(prevLen) < 254 {
entry = append(entry, byte(len(prevLen))) // 1B
} else {
entry = append(entry, 0xFE) // 标记
entry = append(entry, uint32ToBytes(len(prevLen))...) // 4B
}
// 2. 编码 data
// 如果 data 是数字, 尝试用整数编码以节约空间
if v, ok := tryIntEncode(data); ok {
entry = append(entry, v...) // 整数编码: 1-9B
} else {
// 字符串编码
entry = append(entry, encodeStrLen(len(data))...) // 1/2/5B
entry = append(entry, data...) // N B
}
return entry
}mermaid
flowchart LR
subgraph ZIP["ziplist 内存布局 (实际数据)"]
ZB["0x2B000000<br/>43B总长"] --> ZT["0x26000000<br/>尾偏移38"]
ZT --> ZLEN["0x0300<br/>3个元素"]
ZLEN --> E1["[0x00] [0x04 hell] [o]<br/>prev=0, 5B str"]
E1 --> E2["[0x06] [0xF6 5] [world]<br/>prev=6B, strlen+5B"]
E2 --> E3["[0x0E] [0xD2 100]<br/>prev=14B, int16=100"]
E3 --> ZEND["0xFF<br/>结束"]
end
style ZB fill:#607D8B,color:#fff
style ZT fill:#607D8B,color:#fff
style E1 fill:#2196F3,color:#fff
style E2 fill:#FF9800,color:#fff
style E3 fill:#4CAF50,color:#fff
style ZEND fill:#F44336,color:#fff8.3 ziplist 的致命缺陷：级联更新（Cascade Update）
初始状态: E1(250B) → E2(prevlen=1B) → E3(prevlen=1B) → ...
如果 E1 从 250B 更新为 254B:
Step 1: E1 变长 → E2 的 prevlen 需要更新
Step 2: 原来 prevlen=1B (存250), 现在需要5B (存254)
Step 3: E2 从 (1B prevlen + 1B encoding + data) 额外多 4B → E2 变长了！
Step 4: E3 的 prevlen 也要跟着变（1B→5B）→ E3 也变长了！
Step 5: E4... E5... → 连锁反应直到某个 entry 恰好长度不变
最坏情况: O(n²) 次内存移动！这就是 ziplist 的级联更新问题（cascade update）——链式反应最坏情况下会导致大量内存重分配和移动。
8.4 listpack — Redis 7.0 的解决方案
核心洞察：级联更新的根源是 prevlen 编码了前一个 entry 的长度。那我存自己的长度不就行了？
listpack 布局:
┌───────────┬───────────┬─────────────────┬──────┐
│ tot-bytes │ num-elem │ element1 ... N │ end │
│ 4B │ 2B │ 变长 │ 1B │
└───────────┴───────────┴─────────────────┴──────┘
element = <encoding> <data> <backlen>
backlen: 当前 element 自己的长度，存尾部，支持反向遍历
├─ 0xxxxxxx: 1B, 存 0-127
├─ 01xxxxxx: 2B
├─ 001xxxxx: 3B
├─ 0001xxxx: 4B
└─ 00001xxx: 5B, 存更大长度mermaid
flowchart LR
subgraph ZL["ziplist: 更新 E1 触发链式反应"]
ZE1["E1: 250→254B"] --> ZE2["E2 prevlen: 1B→5B<br/>E2 变长 4B!"]
ZE2 --> ZE3["E3: prevlen 也要变<br/>→ 继续传播"]
ZE3 --> ZE4["E4... E5... 😱"]
end
subgraph LP["listpack: 只存自己长度, 没影响"]
LE1["E1: 250→254B<br/>backlen: 1B→2B"] --> LE2["E2: 不受影响 ✅"]
LE2 --> LE3["E3: 不受影响 ✅"]
end
ZL -.- LP
style ZE4 fill:#F44336,color:#fff
style LE2 fill:#4CAF50,color:#fff
style LE3 fill:#4CAF50,color:#ffflistpack 的反向遍历：
正向: tot-bytes → element1 → ... → elementN
反向: elementN → 读取尾部 backlen → 算出 elementN-1 的位置 → ...
不需要知道前驱是谁，只需知道前驱的结束位置 = 当前位置 - 前驱的 backlen 表示的字节数8.5 quicklist — ziplist + 双向链表的混合
Redis 3.2 引入的 List 专用结构：
quicklist:
┌───────┐ ┌───────┐ ┌───────┐
│ quick │ │ quick │ │ quick │
│ node │↔ │ node │↔ │ node │
│ │ │ │ │ │
│┌─────┐│ │┌─────┐│ │┌─────┐│
││ziplist│ ││ziplist│ ││ziplist│
│└─────┘│ │└─────┘│ │└─────┘│
└───────┘ └───────┘ └───────┘
每个 quicklist node 内部的 ziplist 控制在约 8KB
→ 享受链表 O(1) 头尾操作 + ziplist 的内存紧凑
→ 避免纯 ziplist 过大时的级联更新风险8.6 对比总结
| 特性 | ziplist | listpack | quicklist |
|---|---|---|---|
| 内存布局 | 连续 | 连续 | 双向链表 + 片段 |
| 级联更新 | ❌ 存在 | ✅ 无 | ✅ 限制在 8KB 内 |
| 反向遍历 | prevlen | backlen | 链表 + prevlen |
| Redis 版本 | ≤6.x (List/Hash/ZSet) | 7.0+ (Hash/ZSet) | 3.2+ (List) |
| 适用元素数 | <512 | <512 (Hash) / <128 (ZSet) | 无限制 |
| 内存效率 | 极高 | 极高 | 高 |
9.5 工程实践：链表 vs 数组的 Cache 局部性
为什么教科书说"链表 O(1) 插入"，但实际性能常不如数组？
| 操作 | 链表理论复杂度 | 数组理论复杂度 | 实际性能（小规模 n<1000） |
|---|---|---|---|
| 遍历 n 个元素 | O(n) | O(n) | 数组快 5-10× |
| 随机插入（已知位置） | O(1) | O(n) | n<100 时数组可能更快 |
| 头部插入 | O(1) | O(n) | 链表确实更快 |
| 查找第 k 个 | O(k) | O(1) | 数组快 |
根本原因：Cache Line 和预取
数组遍历:
CPU 读 arr[0] → 整个 cache line (64B) 被加载 → arr[1]~arr[7] 已在 L1
→ 连续 8 个 int 只需 1 次内存访问
→ CPU prefetcher 自动预取下一个 cache line
→ 实际每个元素访问 ~1ns
链表遍历:
CPU 读 node1 → 获取 node1.next 指针 → 跳到 node2 的地址
→ node2 可能在完全不同的内存页上
→ L1 miss → L2 miss → 可能 L3 miss → 访问 DRAM
→ 实际每个元素访问 ~5-100ns（取决于 cache 命中率）mermaid
flowchart LR
subgraph "数组: 连续内存, prefetch 友好"
A1["Cache Line 1<br/>[0][1][2][3][4][5][6][7]"] --> A2["Cache Line 2<br/>[8][9][10][11][12][13][14][15]"]
A2 --> A3["Cache Line 3<br/>..."]
end
subgraph "链表: 随机跳转, cache miss"
L1["Node@0x1000"] -->|"next"| L2["Node@0x5F00"]
L2 -->|"next"| L3["Node@0x2A80"]
L3 -->|"next"| L4["Node@0x9100"]
end实际 Benchmark 数据
text
遍历 10000 个 int（Go, AMD Ryzen 5800X）:
[]int slice: ~2.5μs (每元素 ~0.25ns, L1 命中)
*list.List: ~45μs (每元素 ~4.5ns, 大量 L2/L3 miss)
[]*int (指针数组): ~12μs (每元素 ~1.2ns, 一次间接跳转)
结论: 链表遍历比数组慢 ~18×（这个差距随数据量增大而增大）那链表什么时候真正有优势？
| 场景 | 为什么链表更好 | 典型系统 |
|---|---|---|
| 频繁在中间插入/删除 | 数组需要 memmove，链表只改指针 | LRU Cache（已知节点位置） |
| 元素极大，移动代价高 | 链表只移动指针（8B），不移动数据 | Linux 内核进程链表 |
| 需要同时挂在多个集合 | 侵入式链表，一个对象多个 list_head | Linux 内核各种队列 |
| 不需要随机访问 | 只需顺序遍历或头尾操作 | 消息队列、事件队列 |
| 内存碎片不是问题 | 有专用内存池 | 内核 slab 分配器 |
Redis 为什么从链表转向 ziplist/listpack？
text
Redis 早期 List 实现: 双向链表 (adlist)
每个节点: prev(8B) + next(8B) + value指针(8B) + malloc头(16B) = 40B 开销
存一个 "hello"(5B): 实际占用 45B，有效载荷率 = 5/45 = 11%
Redis 3.2+ List 实现: quicklist (ziplist 链表)
ziplist 内: 每个 entry 只有 2-10B 开销
存一个 "hello"(5B): 实际占用 ~8B，有效载荷率 = 5/8 = 62%
内存节省: ~6× (对于小元素)
性能: ziplist 连续内存 → cache 友好 → 遍历更快这就是"理论复杂度相同，但工程实现选择不同"的典型案例。
工程选型决策树
mermaid
flowchart TD
A["需要线性集合"] --> B{"需要随机访问?"}
B -->|是| C["数组/Slice"]
B -->|否| D{"频繁中间插入删除?"}
D -->|否| E["数组/Slice<br/>(cache 友好)"]
D -->|是| F{"已知节点位置?"}
F -->|是| G["双向链表<br/>(O(1) 删除)"]
F -->|否| H{"元素很大?"}
H -->|是| I["链表<br/>(避免移动大对象)"]
H -->|否| J["数组<br/>(小元素移动代价低)"]核心原则：除非你有明确的"频繁中间插入/删除 + 已知节点位置"的需求，否则默认用数组/Slice。现代 CPU 的 cache 优势使得数组在绝大多数场景下都更快。
10. 各语言实现对比
| 结构 | C++ STL | Go | Rust | Python |
|---|---|---|---|---|
| 双向链表 | std::list | container/list | LinkedList(std) | collections.deque |
| 动态数组 | std::vector | []T slice | Vec<T> | list |
| 栈 | std::stack | 用 slice 模拟 | Vec 模拟 | list |
| 队列 | std::queue | 用 slice + channel | VecDeque | collections.deque |
| 优先队列 | std::priority_queue | container/heap | BinaryHeap | heapq |
| 双向队列 | std::deque | 无内置 | VecDeque | collections.deque |
登录后即可发表评论 👇