Ach*_*int 3 c tree linked-list
为什么存储分配器使用循环链表来存储分配/空闲地址而不是平衡树？遍历链表需要O(n)的复杂度,而平衡的树可以遍历O(logn),对吗？它背后的优势/推理是什么？
前提("存储分配器使用循环链表来存储分配/空闲地址")不一定正确.某些分配器可能也是如此,但总的来说并非如此.
如果分配器使用类似链表的结构来跟踪存储器块,则它通常作为元数据嵌入存储器块本身 - 即.而不是作为一个单独的数据结构.
例如,每个内存块可以以状态(空闲/已分配)和块的大小开始.这种方法基本上实现了一个链表(使用大小,你可以很容易地确定下一个块的起始地址),但它有链接列表没有的其他属性:你仍然可以找到一个特定的内存块(节点)通过了解其内存地址.
因此,您有一个O(1)访问时间(因为您或编译器知道内存块的内存地址).合并相邻的免费区块也很简单.如果需要运行某种去碎片或压缩算法,可以使用类似链表的结构来完成.找到足够大小的空闲块也可以使用类似链表的结构来完成(尽管有时第二个嵌入式链表特别用于空闲块,以最小化分配函数的开销).
当然,这只是解决问题的一种方法.但它表明,使用链表不一定是比另一个数据结构更糟糕的选择.