Searching linked lists

[debiandude]

Any one know of a good method to search through a linked list. Right now Im doing it linearly and I can't think of a way to make it faster.

[chris_i386]

I'm not sure wheter I got you right...
You could try to split your list into many smaller lists,
and then store each list item depending on its hash value
in one of these lists.
Then you only need to search one of these short lists.
Are you programming in C?

[chris_i386]

Argh, my grammar!
I think
"and then store each list item in one of these lists, depending on its hash value."
should be correct, though.

[debiandude]

Yeah its C and a doubly linked list. What your asking me to do is create a binary tree or something. That seems a little overkill. I just want a little bit better of a way they going through the whole list. But now that I think of it its not like an array where I can just jump from one end to the other, so perhaps I can't get a much better way.

[chris_i386]

Hm. I don't know what a double linked list is...
But maybe if you explain what you're trying to do with your
program I could still help you.
Could you give a code sample?

[debiandude]

A double linked list is a structure that has pointers to both the next and previous members.

so member b would have a pointer to its previous a and to its next c. Its a long chain. A binary tree is differnt, its like small little doubly linked list. You have a root node a which has a pointer to b and c, now both b and c point back to a but they also point foward to two more V shaped things.

Its not really a metter of helping me. I was being stupid before, I can't do better than a sequential search in my linked lists.

And I don't want to change all the functions I wrote now to become a tree and have all the recurious and stuff.

[Energon]

Well, to be honest, the answer will most likely be no. Unless you put some kind of rule into the list to make searching happen based on sets of rules, it's going to be linear... but, that's okay because by definition, searching is linear... that's why binary search trees were made... :)

It may seem like a lot of overhead, but when you consider how much faster lg(n) is over n, it's well worth it. Now, if you know that your list will never grow over a small data set (or even better, if you know the exact size), you can use a hash table, or just stick with a list since small amounts aren't very slow considering all things...

[truls]

I agree with Energon.

The only thing I can think of is if you know something about the usage of the data. Like if you keep a pointer to the most recently visited element, knowing that the user usually fetches the next one. Other than that you need to know something about the data or the usage of the data to be more clever.

[mingshun]

Is this your school work? :p
Last time, I code my own table to solve this "fastest search" problem. I builld an array of linked-list.

[0] - linkedlist
[1] - " "
[2] - " "
.
.
.

Then I compute the hash value of the key in the data and slot it into the array index. The trick here lies in how you come out with a good hash value. (Okay, I know this is still not good enough but I think it is at least *doable* for students :p)

[Energon]

The question is, how did you handle collisions in your hash table? You're basically doing what I suggested, but it's only good if you've got a good hashing function (there are lots out there), you know the size of your data set (and can get a rough idea of the amount of collisions possible), and you handle collisions in an efficient manner...

Which leads me to think that a binary search tree is probably the way he should go... :)

[mingshun]

Originally posted by Energon
The question is, how did you handle collisions in your hash table?

Way 1:
I insert them in the linkedlist...
Remember I drew the "table" diagram earlier on?

Way 2:
My lecturer taught us to hash it again (but she taught in theory while we code :( ) ... Hence a table can have 2 to 3 layers of hash ...



You're basically doing what I suggested, but it's only good if you've got a good hashing function (there are lots out there), you know the size of your data set (and can get a rough idea of the amount of collisions possible), and you handle collisions in an efficient manner...


Yah, I didn't deny that :)
And no, I don't know how big my data set is. I just build a very very big array of linkedlist. And I mod the hash value of my data to the size of these arrays. And I used Java to code. Hence at the end of the day (I used vector since vector is a special linkedlist), I just had a very big array of vectors.

It is kind of difficult to explain over the net.
But that solves my data structure problem and I can move on to other areas ...


Which leads me to think that a binary search tree is probably the way he should go... :)

Actually, binary search tree has the danger of becoming linked-list like if it is very skewed ... It is better to build a self-balancing AVL tree...

Well, no one says that programming is easy :p

[Energon]

Heh... I forgot that you had done it as lists... :)

And you're definitly right about binary search trees becoming linear if not done properly... but if you're really looking to improve the search speed without wasting space as you do with a hash table, then a balanced tree is the only way to go. The only problem with a balanced tree is that deletions can be slow as piss because of the re-balancing.

So many choices... ;)

[debiandude]

Woah. Thanks for all the input so far. I still havn't decied on what I'm going to do, but I am leaning to change it to a binary tree.

Oh and someone asked if this was for school, its not its for work. Do people acutally start school this early? I don't start until Sept 3rd, thank god, oh college me so nervous and excited!

Okay here is a little more info. I have this struct that sorta like this:

struct _thing {
double number;
char string[BUF];
int seq;
int row_num;
_thing *next;
_think *prev;
} thing;


I get all my data back from the data base sorted alphabetically so as an example I might have

{ 1.3, "A", 1, 1 }
{ 0.8, "B", 3, 2 }
{ 4.7, "C", 2, 3 }

All this data going into a table so row_num refers to its position in the table. Now although it comes back from the database sorted by string, some times people want it sorted by number or sequence. So I wrote a merge sort that would just switch the row positoin and not actually move the pointers and then just update the table since the rows would change.

Now with the information would a binary tree be easy to do. Im trying to picture in my head how I would deciede how the next new item would go left or right, but I can't see it. Also how easy would it be to sort the tree for the other values. I don't need to actually more the pointers I just need to change the row values. Thanks again.

[debiandude]

I should note that chaning is not of dire need because even though searching though the list for an item to update is at worst n, n has yet to be very large. However, if it ever does get very big (the assured me it will never get x high, but Ive been told something like that before and it blew up in my face when one day they got 5 * x) the searches will take very long and I will probably get heat for it.

Does any one have any good example to look at also.

[mingshun]

Originally posted by debiandude

Oh and someone asked if this was for school, its not its for work. Do people acutally start school this early? I don't start until Sept 3rd, thank god, oh college me so nervous and excited!


Oh, I live in Singapore and here, it is summer through the whole year. I have no idea when does school start over your side :p



{ 1.3, "A", 1, 1 }
{ 0.8, "B", 3, 2 }
{ 4.7, "C", 2, 3 }


Basically, the algo for bst is something like this:


struct* thing insert ( tree, data) {
if (tree == NULL)
correct position, build the node and link it;

else if (data > tree->key)
insert (right_sub_tree, data);

else if (data < tree->key)
insert (left_sub_tree, data);

else printerr ("Duplicate items");
}


For a height of 5 to 6, I don't think it is that bad.
But will you get something like 100 million data? If that is the case, you have to research more. ie: A B+ tree is more appropriate then.