I think the allocation of address in case of circular linked list is very fast ---- O(1), whereas it takes O(log n) in case of balanced tree.
And yes, to find address for deletion in case of circular linked list is expensive... O(n) in worst case. On Tue, Jul 12, 2011 at 6:19 AM, aanchal goyal <goyal.aanch...@gmail.com> wrote: > why does space allocator malloc()/free() interface use circular link list to > store allocated/freed addresses in sorted order in a link list form and not > tree(balanced)? To find some address for deletion it needs list traversal > which costs O(n) whereas a balanved tree (at cost of extra pointer space ) > can reduce this cost to O(log n)? There are lots of other issues with list > usage here for which i think tree would be better . > > -- > Regards, > Aanchal Goyal. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
