Click here to Skip to main content
15,902,893 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
Hi friends, i know the program in O(1) deletion in linked list but O(log n) time complexity how can I proceed for logic. Please help me for logic...

What I have tried:

Tried using heap search but can't able to achieve...
Posted
Comments
jeron1 12-Dec-23 12:51pm    
Possibly do a binary search on a sorted list, then delete?

 
Share this answer
 
v2
O(1) refers to the performance cost scaling linearly with complexity. The only way to reduce that is to use a collection with efficient searching capability. A linked list is not efficient at searching. An unordered_map[^] from the Standard Template Library is an example of a collection with VERY efficient searching. A hash table[^] is a generic example of a high performance collection. The hash table is probably a good example to pursue if you have to implement it yourself since it is fairly simple.
 
Share this answer
 
You cannot achieve a better performance of O(1) on a arbitrary linked list.
In order to obtain a better time complexity, you have to use a ordered list (pardon the pun). Then you may perform a binary search.
 
Share this answer
 
Quote:
Please help me for logic.

I fear there is no such logic, or it is not linked list anymore.
Linked list is a data structure, and each data structure have its own set of advantages and disadvantages, you choose the data structure depending on your usage of the data.

If you have copy the list to another data structure to perform heap search the cost of building that structure us usually more than the gain of using that structure.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900