@aanchal u are correct in first case.
deletion is also not O(1). because while freeing we pass the address. so with that address it can directly reach the node which is to be freed. Thanks Santosh On Tue, Jul 12, 2011 at 7:32 PM, ankit sambyal <ankitsamb...@gmail.com>wrote: > 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. > > -- 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.
