@aanchal correction: deletion is also O(1);
On Tue, Jul 12, 2011 at 8:31 PM, santosh mahto <santoshbit2...@gmail.com>wrote: > @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.
