We help IT Professionals succeed at work.

To decrease the search time in a link list

DineshJolania
on
Medium Priority
360 Views
Last Modified: 2010-04-15
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 ?.
Comment
Watch Question

CERTIFIED EXPERT
Top Expert 2006
Commented:
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.

Cheers!
Sunnycoder

Not the solution you were looking for? Getting a personalized solution is easy.

Ask the Experts
Commented:
Use a binary tree (or a combined doubly linked list and a tree)

Author

Commented:
Hi Sunny,
You mean  "Hash table for contents of node and the node address" ?
Thanks
Dinesh

Author

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.
Thanks

Commented:
Hi DineshJolania

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

Commented:
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.



CERTIFIED EXPERT
Top Expert 2006

Commented:
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.

Cheers!
sunnycoder
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.

Paul

Author

Commented:
Thanks for valuable suggestions .
Access more of Experts Exchange with a free account
Thanks for using Experts Exchange.

Create a free account to continue.

Limited access with a free account allows you to:

  • View three pieces of content (articles, solutions, posts, and videos)
  • Ask the experts questions (counted toward content limit)
  • Customize your dashboard and profile

*This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

OR

Please enter a first name

Please enter a last name

8+ characters (letters, numbers, and a symbol)

By clicking, you agree to the Terms of Use and Privacy Policy.