显式空闲链表

隐式空闲链表通过头部中的大小字段隐含地连接空闲块
显式空闲链表在空闲块中使用指针连接空闲块

将空闲块组织为某种形式的显式数据结构。因为根据定义，程序不需要一个空闲块的主体，所以实现这个数据结构的指针可以存放在这些空闲块的主体里面。例如，堆可以组织成一个双向空闲链表，在每个空闲块中，都包含一个 pred(前驱) 和 siicc(后继) 指针

显式空闲链表的实现

• 保留空闲块链表, 而不是所有块
  • “下一个” 空闲块可以在任何地方
    • 因此我们需要存储前/后指针，而不仅仅是大小
  • 还需要合并边界标记
  • 幸运的是，我们只跟踪空闲块，所以我们可以使用有效区域
    逻辑上，我们通过这个双向的链接使得它在遍历上是顺序有序的，但是事实上，物理地，块的顺序是任何的，对于空闲块的连接往往是乱序的
    

显示空闲链表分配空闲块

释放空闲块

使用双向链表而不是隐式空闲链表，使 首次适配 的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。不过，释放一个块的时间可以是线性的，也可能是个常数，这取决于我们所选择的空闲链表中块的排序策略

LIFO 后进先出的顺序维护链表

将新释放的块放置在链表的开始处。使用 LIFO 的顺序和首次适配的放置策略，分配器会最先检查最近使用过的块。在这种情况下，释放一个块可以在常数时间内完成。如果使用了边界标记，那么合并也可以在常数时间内完成

按照地址顺序来维护链表

其中链表中每个块的地址都小于它后继的地址。在这种情况下，释放一个块需要线性时间的搜索来定位合适的前驱。平衡点在于，按照地址排序的首次适配比 LIFO 排序的首次适配有更高的内存利用率，接近最佳适配的利用率

一般而言，显式链表的缺点是空闲块必须足够大，以包含所有需要的指针，以及头部和可能的脚部。这就导致了更大的最小块大小，也潜在地提高了内部碎片的程度

回顾

优势

使用双向链表而不是隐式空闲链表，使首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间。不过，释放一个块的时间可以是线性的，也可能是个常数，这取决于我们所选择的空闲链表中块的排序策略

缺陷

内部碎片加大了，因为原本一个已分配块的空白有效区域中，填充了下一个和上一个的指针，内部冗余了