Using a circular linked list as a balanced binary v / s free list search tree when allocating and freeing dynamic storage

Question

The disadvantage of a linked list is that for malloc () a piece, the memory allocator should look for a list of links, and then if that address is found, return it. So why not use a binary tree to reduce search time?

One of the questions asked by NVIDIA is http://www.careercup.com/question?id=9765724

Found a related article discussed here

Answer 1

If I understand you correctly, check this link:

Temporary memory allocation complexity

Heap allocation can be done by presenting free memory as a linked list, but any reasonably sophisticated memory manager will use something faster, like the AVL tree mentioned in the answer in the question I posted. There is even an O (1) solution called TLSF (Two Level Segregated Fit), also mentioned in the answer.