空闲链表是标记-清除算法中管理外部碎片最常用方案，通过顺序、分离或带边界标签的链表组织空闲块，并结合首次/最佳/邻近适配策略分配，辅以合并与优化机制提升效率。
标记-清除算法本身不移动对象，因此会留下大量不连续的空闲内存块，导致外部碎片。为高效利用这些碎片，空闲链表是最常用且直接的管理方案。
空闲链表的基本结构
将所有大小不一的空闲块按地址顺序或大小顺序组织成单向或双向链表。每个空闲块头部通常包含两个字段：前驱指针（可选）、后继指针，以及记录自身大小的字段。有些实现还会在块尾部冗余存储大小信息，便于合并时快速定位相邻块。
- 顺序链表：按起始地址升序排列，利于首次适配（First Fit）分配
- segregated 链表：按大小分桶，多个链表分别管理不同尺寸范围的空闲块，提升查找效率
- 带边界标签的链表：在每个空闲块前后都设置“边界标签”，明确标识占用/空闲状态，便于相邻块合并
分配时的策略选择
从空闲链表中选取合适块的过程直接影响内存利用率和分配速度。常见策略有：
- 首次适配（First Fit）：从链表头开始扫描，返回第一个足够大的空闲块。速度快，但易在低地址积累小碎片
- 最佳适配（Best Fit）：遍历全链表，选最接近请求大小的空闲块。减少浪费，但可能留下难以利用的微小碎片，且搜索开销大
- 邻近适配（Next Fit）：从上次分配位置继续搜索，平衡局部性与遍历成本，适合频繁分配场景
回收与合并的关键操作
当对象被标记为垃圾并清除后，对应内存区域被插入空闲链表。关键在于检查其前后是否也为空闲块，并执行合并，避免碎片细化。
- 通过边界标签或内存布局约定，快速判断前驱/后继块是否空闲
- 合并时更新链表指针，调整大小字段，删除被合并的中间节点
- 若采用双向链表，合并操作只需常数时间；单向链表则需额外维护前驱信息或遍历查找
实际优化考虑
纯空闲链表在高负载下可能面临性能瓶颈，工程实践中常辅以其他机制：
- 引入分离存储（segregation）：对小对象使用固定大小块池，规避小碎片问题
- 周期性触发空闲链表整理：按地址排序、合并零散小块，或触发压缩式GC作为补充
- 缓存最近释放的块（free list cache）：减少高频小分配对链表遍历的依赖
空闲链表不是万能解法，但它轻量、可控，与标记-清除天然契合。设计时需权衡查找开销、合并复杂度与碎片控制效果，根据应用内存访问模式选择合适变体。
