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

Question

存储分配器如何使用循环链表来存储分配/空闲地址而不是平衡树？遍历链表需要O（n）的复杂性顺序，而平衡树可以在O（logn）中遍历，对吗？背后有什么优势/推理？

Answer 1

前提（“存储分配器用来存储分配/释放地址循环链表”）未必是真实的。对于某些分配器来说可能是这样，但通常情况并非如此。

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

例如，存储器的每个块可以与状态（空闲/分配），并且块的尺寸开始。这种方法基本上实现了一个链表（使用大小，你可以很容易地确定下一个块的起始地址），但是它还有链表不具有的其他属性：你仍然可以找到一个特定的内存块（节点）通过知道它的内存地址。

所以，你有一个O（1）访问时间（因为你，或者编译器，知道的内存块的内存地址）。合并相邻的空闲块也很简单。如果需要运行某种去碎片或压缩算法，可以使用类似链表的结构来完成。寻找一个足够大小的空闲块也可以使用类似链表的结构来完成（尽管有时第二个嵌入链表专门用于空闲块，以最小化分配函数的开销）。

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

Answer 2

嗯，分配器是经常特制的，非常认真，特别制作的，以他们预期的服务的特殊需求。

因此，有可能更复杂，在很多工业实力分配器发现少了规则的结构。

不过，假设你的问题的前提是准确的：

最坏的情况的复杂性是最相关的非常大的遍历。大多数分配器的设计都是这样，所需的遍历通常很小，非常小，以至于维护平衡树所需的额外开销会使平均情况下的遍历速度变慢。此外，工程师们更喜欢最简单的解决方案，除非更复杂的解决方案明显更好：循环链接列表只是简单的。

Answer 3

遍历链表需要复杂的O（n）的顺序

是的，但存储分配器的目的是提供一些分配的空间，而这并不一定需要“穿越”存储以前分配的结构。例如，如果我们每次都在特定大小的块中分配内存（所以我们在结构中保留了这种大小的块），那么我们只需要返回第一块。一般来说，我们只需要找到一个足够大的节点，所以我们看看，直到找到足够大的节点（这通常会很快发生）。

而在O（logn）中可以遍历一棵平衡树，对不对？

，我们可以发现在O（LOGN）特定的元素，但在那个时候，我们不能“穿越”的树，因为根据定义的数据结构的“穿越”是指访问每一个节点，且有是O（n）个节点。如果树具有合适的搜索树属性，我们只能“在O（logn）中找到特定的元素，我们又想要哪个节点？这将使我们有效地找到，例如，足够大的最小分配;但无论如何，这并不一定是我们想要回报的东西（因为这种政策导致大量的小块可能适用于或可能不适合未来分配，并且结构膨胀）See also。