Hallo. In a project i''m working, i was in need of linked list. However, i need to perform a very quick search on this list, occasionaly. Lets just say that this is propably the part that needs most optimization. Now, this linked list i sorted, using a numeric key. The sort is from 0..n where (n>0). I would implement the binary search, but for binary search to work, i need to know the middle, something that in my case is almost impossible (not to say impossible). Any ideas on how to perform a very fast search? PS: The amount of items of the list is not fixed (no Max exists). Thanks.

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

Hash Table???? Any place i can read any documents on this Hash Table?

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.