存储分配器如何使用循环链表来存储分配/空闲地址而不是平衡树？遍历链表需要 O(n) 阶的复杂性，而平衡树可以在 O(logn) 中遍历，对吗？它背后的优势/原因是什么？
最佳答案
前提(“存储分配器使用循环链表来存储分配/空闲地址”)不一定正确。对于某些分配器来说可能是正确的，但一般情况下并非如此。
如果分配器使用类似链表的结构来跟踪内存块，它通常作为元数据嵌入内存块本身 - 即。不是作为一个单独的数据结构。
例如，每个内存块都可以从状态(空闲/已分配)和 block 的大小开始。这种方法基本上实现了一个链表(使用大小，可以很容易地确定下一个 block 的起始地址)，但是它具有链表没有的其他属性:您仍然可以找到特定的内存块(节点)通过知道它的内存地址。
因此，您的访问时间为 O(1)(因为您或编译器知道内存块的内存地址)。合并相邻的空闲 block 也很简单。如果需要运行某种碎片整理或压缩算法，可以使用类似链表的结构来完成。也可以使用类似链表的结构来找到足够大小的空闲 block (尽管有时第二个嵌入式链表专门用于空闲 block ，以最大限度地减少分配函数的开销)。
当然，这只是解决该问题的一种可能方法。但这表明使用链表并不一定是比其他数据结构更糟糕的选择。
关于c - 为什么在存储分配器中使用循环链表而不是树？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7136790/