寻求O(1)时间复杂度且零额外内存占比的alloc/free实现方案

要实现O(1)时间的alloc()和free()，同时做到零额外内存开销（即元数据完全复用空闲块空间，无专门预留的管理内存），我们可以采用基于栈的显式空闲链表方案，核心思路是让空闲块自身充当链表节点，仅在块空闲时用其空间存储链表指针，分配后完全交付用户使用。

方案细节拆解 #

1. 内存块划分

把起始地址为P的1MB内存，拆成连续的16B小块，总共能得到 1024*1024 / 16 = 65536 个块，每个块的地址为 P + 16*i（i从0到65535）。

2. 空闲块的复用设计

当块处于空闲状态时，它的16B空间被用作链表节点（以64位指针为例）：

• 前8字节：存储下一个空闲块的地址（即链表的next指针）
• 后8字节：无特殊用途（如果需要双向链表可以存prev，但单链表足够实现O(1)操作）
  当块被分配时，整个16B空间完全交给用户，原有的链表指针会被用户数据覆盖——因为这些块本来就是空闲的，用来存管理数据不算占用用户可用内存，完全符合“零额外内存占比”的要求。

3. 初始化：构建栈式空闲链表

把所有空闲块连成一个单链表（栈结构）：

• 第一个块（地址P）的next指针指向第二个块（P+16）
• 第二个块的next指针指向第三个块（P+32）
• ...
• 最后一个块的next指针设为NULL（标记链表末尾）
• 我们只需要一个栈顶指针来记录当前链表的第一个空闲块，这个指针可以直接存在内存块的某个固定位置（比如最后一个块的前8字节）——但注意：当所有块都被分配时，alloc()不会被调用（题目保证调用alloc()时总有空闲空间），此时这个存储栈顶的块也可以被分配，完全不浪费内存。

4. O(1)时间的alloc()实现

每次分配直接取栈顶的空闲块，然后更新栈顶为该块的next指针：

void* alloc() {
    // 假设stack_top存在给定内存的固定位置，比如最后一个块的前8字节
    void** stack_top = (void**)(P + 16*(65536-1));
    void* curr_block = *stack_top;
    // 更新栈顶为当前块的下一个空闲块
    *stack_top = *(void**)curr_block;
    return curr_block;
}

5. O(1)时间的free()实现

每次释放直接把块压入栈顶，更新栈顶指针即可：

void free(void* p) {
    void** stack_top = (void**)(P + 16*(65536-1));
    // 把当前块的next指针指向原栈顶
    *(void**)p = *stack_top;
    // 更新栈顶为当前释放的块
    *stack_top = p;
}

核心优势 #

• O(1)时间复杂度：alloc()和free()都是简单的指针操作，没有遍历开销。
• 零额外内存占比：所有管理用的链表指针都存储在空闲块内部，没有专门预留的元数据内存；当所有块都被分配时，100%的内存都能被用户使用。

备注：内容来源于stack exchange，提问作者shinzou