回答思路

得分点 隐式链表，显示空闲链表 标准回答 malloc() 的整体思想是先向操作系统申请一块大小适当的内存，然后自己管理，即内存池。 malloc() 分配空间有一个数据结构，允许它来区分边界，区分已分配和空闲的空间，数据结构中包含一个头部信息和有效载荷，有效载荷的首地址就是 malloc() 返回的地址，可能在尾部还有填充，为了保持内存对齐。头部相当于该数据结构的元数据，其中包含了块大小和是否是空闲空间的信息，这样可以根据头地址和块大小的地址推出下一个内存块的地址，这就是隐式链表。 malloc() 基本的实现原理就是维护一个内存空闲链表，当申请内存空间时，搜索内存空闲链表，找到适配的空闲内存空间，然后将空间分割成两个内存块，一个变成分配块，一个变成新的空闲块。如果没有搜索到，那么就会调用 sbrk() 推进 brk 指针来申请内存空间。搜索空闲块最常见的算法有：首次适配，下一次适配，最佳适配。 - 首次适配：第一次找到足够大的内存块就分配，这种方法会产生很多的内存碎片。 - 下一次适配：也就是说等第二次找到足够大的内存块就分配，这样会产生比较少的内存碎片。 - 最佳适配：对堆进行彻底的搜索，从头开始遍历所有块，使用数据区大小大于 size 且差值最小的块作为此次分配的块。 在释放内存块后，如果不进行合并，那么相邻的空闲内存块还是相当于两个内存块，会形成一种假碎片。所以当释放内存后，需要将两个相邻的内存块进行合并。 还有一种实现方式则是采用显示空闲链表，这个是真正的链表形式。在之前的有效载荷中加入了前驱和后驱的指针，也可以称为双向链表。维护空闲链表的的方式第一种是用后进先出（LIFO），将新释放的块放置在链表的开始处。另一种方法是按照地址的顺序来维护。