链表Linked list
通过指针连接元素，调整链接完成插入或删除。
- 核心约束
- 节点以链接确定顺序，内存位置不必连续。
- 适用问题
- 频繁摘除、重排已知节点，侵入式对象管理。
- 边界与取舍
- 指针占用空间；遍历的缓存局部性通常较差。
常见操作#
n 为节点数；以下常数时间操作假定已拿到所需节点。
| 操作 | 时间复杂度 | 条件与说明 |
|---|---|---|
| 按位置 / 按值查找 | 链表没有下标到地址的直接映射，最坏需顺着链接遍历。 | |
| 头部插入 / 删除 | 更新固定数量的指针；节点分配与释放另计。 | |
| 已知位置插入 | 单链表须已知前驱；双向链表可以在已知节点前后插入。 | |
| 删除已知节点 | 双向链表；单链表通常还需要前驱，寻找前驱最坏 。 | |
| 尾部追加 | 维护尾指针；没有尾指针时需要 寻尾。 | |
| 遍历 / 构建 | 访问每个节点；构建假定单个节点分配视作常数操作。 |
时间与空间#
- 时间复杂度
- 定位 ；已知位置修改
- 存储空间
每个节点另存一个或两个链接；不包含外部分配器元数据。
工程中的应用#
10 个案例 · 附源码伙伴分配器把空闲物理页组织为不同 order 的连续块，并用空闲链表管理同阶块。
附源码片段 · 内存管理
limit_req 把漏桶计算、红黑树查状态与队列回收组合起来，按配置的 key 管理请求速率。
附源码片段 · 通信与流量
QEMU 的 QEMUTimerList 用有序单链表维护定时器，链表头就是下一到期项。
附源码片段 · 调度与资源分配
缓存块命中后可能需要从队列中间移除，双向链表让这一步保持常数时间。
附源码片段 · 内存管理
Redis List 提供左右两端的插入和弹出；在 quicklist 编码下，用带头尾指针的双向节点链组织紧凑数据块。
附源码片段 · 内存管理
nginx 按有效权重累加候选节点的得分，选中最高分节点后减去总权重，让请求按权重交错分配。
附源码片段 · 通信与流量
nginx 将小额分配变成池内游标推进，并以池的生命周期统一释放；较大的分配另建记录管理。
附源码片段 · 内存管理
Linux SLUB 将同类对象组织在 slab 中，并用 per-CPU freelist 满足常见分配，避免每次都访问集中管理的部分空闲 slab 列表。
附源码片段 · 内存管理
Linux DRM 使用通用 list_sort 对显示模式链表排序；底层归并通过相等时优先取较早元素来保持稳定性。
附源码片段 · 索引与查找
Linux 把 list_head 嵌入业务对象，通过成员偏移找回宿主，并在编译期检查指针类型。
附源码片段 · 内存管理