You can''t do a search on a linked-list in less than O(n) time. Instead of using a linked-list you might consider instead using a BST or an open hash-table. (or if you''ve got a *lot* of elements a hash-table of BSTs).

A hash table is one of the basic CS data structures. Any good data structures book will probably have a whole chapter devoted to them. I''ll try to give you a simple and brief description of them.

A hash table is a data structure where items are grouped together in "buckets" using a hash function. The hash function is pretty much whatever you need for your purpose.

As an example, let''s say we want to store words where we can quickly check to see if a given word is in the table.

We''ll have 26 buckets, one for each letter of the alphabet. Our hash function will check the first letter of the word and put it in the correct bucket. Notice that once the words are in the bucket, they aren''t ordered. If you hash "hello" and then "has", hello will be put in first.

Now if you want to check and see if a given word is in the table, you go to the correct bucket, then search each item.

There are several different ways of doing all this. You can have a static table in which each bucket has a specific number of "slots" or each bucket can simply be the head node for a link list.

Hash tables can also be combined with other data structures, like SiCrane suggested with BSTs. In this case, each bucket is simply a BST. This way, you can take advantage of the BST searching time to search a bucket, yet you still have the organization of a hash table.