How can I efficiently search a sorted linked list using steps of 1, 10, and 100?

[transgalactic]

i got a sorted linked list from the smallest to the biggest
in each node i can go 1 , 10 ,100 steps forward
i need to find an object in this linked list

if the object is found i need to return it if not then null

what is the most affective way to do that

i can do a simple loop each time it does one step
and then i will surely get the answer

how to use those 10 and 100 step to make it more affective?

i got the skeleton for this function and some missing part:

http://img513.imageshack.us/my.php?image=36394139eh1.gif

i need to fill them with something in order to make it work like they told

 

[Borek]

If you are at the first node you can check what is the number associated with the 100^th node. If it is smaller than the number you are looking for, does it make sense to walk all 100 nodes one by one, or will it be faster to jump 100 nodes ahead in one step?

 

[transgalactic]

but i can't go back
if i go to the 100th and it too big i am stuck there

and i got to stick with this structure thing

 

[Borek]

You are not stuck, you can check value of the other node not leaving current one.

 

[transgalactic]

how can i check the value of the other node without leaving the current one?

 

[Borek]

head->next100->value

You are on your own now.

 

[rootX]

I was thinking about binary search algorithm (log(n)).

Check if next 100 == element
return
if next 100 < element
jump next
else
do with 10..

once you are in less than 10 range. make 1-1 jumps

 

[transgalactic]

i found the solution but i can't understand the logic of it

and i can't understand the meaning of this kind of line (marked red)

Typedef struct forward forward;
Struct forward{
     Int value;
     Forward * next100;
     Forward * next10;
     Forward * next;
};

forward* search_forward(forward * head,ink key){
if(!head)
  return null;

while (head->next100 &&  head->next100->value<=key)
         head=head->next100;

while (head->next10 &&  head->next10->value<=key)
head=head->next10;

while (head->next &&  head->next->value<=key)
head=head->next;if (head->value==key) return head;
return null;
}

 

[rootX]

while (head->next100 && head->next100->value<= key)

keep on going until there is a next 100th pointer
and it has a value less than key value.


see my thing above.. (it also checking that the next 100 exists)

if next 100 < element
jump next 100