c - 为什么在存储分配器中使用循环链表而不是树？

Question

存储分配器如何使用循环链表来存储分配/空闲地址而不是平衡树？遍历链表需要 O(n) 阶的复杂性，而平衡树可以在 O(logn) 中遍历，对吗？它背后的优势/原因是什么？

Answer 1

前提(“存储分配器使用循环链表来存储分配/空闲地址”)不一定正确。对于某些分配器来说可能是正确的，但一般情况下并非如此。

如果分配器使用类似链表的结构来跟踪内存块，它通常作为元数据嵌入内存块本身 - 即。不是作为一个单独的数据结构。

例如，每个内存块都可以从状态(空闲/已分配)和 block 的大小开始。这种方法基本上实现了一个链表(使用大小，可以很容易地确定下一个 block 的起始地址)，但是它具有链表没有的其他属性:您仍然可以找到特定的内存块(节点)通过知道它的内存地址。

因此，您的访问时间为 O(1)(因为您或编译器知道内存块的内存地址)。合并相邻的空闲 block 也很简单。如果需要运行某种碎片整理或压缩算法，可以使用类似链表的结构来完成。也可以使用类似链表的结构来找到足够大小的空闲 block (尽管有时第二个嵌入式链表专门用于空闲 block ，以最大限度地减少分配函数的开销)。

当然，这只是解决该问题的一种可能方法。但这表明使用链表并不一定是比其他数据结构更糟糕的选择。