• C

To decrease the search time in a link list

Hi Experts,
                  To search an element in Link list it takes O(n) time  where n is the number of items.
                   Is there is any way/trick to reduce the search time by considerable amount ?.
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Hi DineshJolania,

Link list is by very nature sequential ... hence there is no way to avoid traversing through it.

However, you can build seach index on the list and use it to route your search queries.
That challange here is to build an index in a manner that insertion and deletion in the list does not become prohibitively expensive.

For example you can build a hash table of values and store a pointer to the node with each value. Insertion is simple because insertion will not affect address of existing nodes and new value can be added to hash table without much expense. Deletion from hash table should not be too difficult either and once again would not affect the existing data.


Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
Use a binary tree (or a combined doubly linked list and a tree)
DineshJolaniaAuthor Commented:
Hi Sunny,
You mean  "Hash table for contents of node and the node address" ?
What were the top attacks of Q1 2018?

The Threat Lab team analyzes data from WatchGuard’s Firebox Feed, internal and partner threat intelligence, and a research honeynet, to provide insightful analysis about the top threats on the Internet. Check out our Q1 2018 report for smart, practical security advice today!

DineshJolaniaAuthor Commented:
Zulti   you mean fusing  link list with binary tree?.
What have learnt about  implementing a link list as a tree will lower the efficency.
Hi DineshJolania

what are your needs from the link list ?
what kind of queries do you intend to perform ?

A linearly linked list can only be searched sequentially, so it's going to be O(n)

A few variations that are somewhat faster:

Have two links per node-- one to the next sequential node, another to the node with the same first character.  That speeds up the search by a factor of 26 to 256 depending on the diversity of the first character.

Generalize the method above so each link points to a subtree-- say the left link to nodes less than the first node, the right node to ones greater.

Hi Dinesh,

I meant hash on contents of the node ... the data

Any method to search faster than O(n) would involve building some kind of index .. it could be a hash table or anything else which fits the bill.

Hi DineshJolania,

If you consider the nature of the data in the list and the data you are searching for you can often reduce the search proces usung one or more of the following:

1. Obviously - Sort the list.
2. Sort the search data first and start your search where you finished last time.
3. If all you need is to know whether the item is in the list or not, there are other techniques such as hash tables.

DineshJolaniaAuthor Commented:
Thanks for valuable suggestions .
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.