linked list search question..

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?i...6394139eh1.gif

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

That is a very unusual linked list.

I have no idea how you know whether there is 1, 10 or 100 elements between the one you are looking for and the one you are currently at - the only way to find that out would be to compare the current one with the ones up ahead, I suppose.

--
Mats

What sort of data elements of the linked list are you dealing with numeric or string??

Quote:

---

Originally Posted by itCbitC

What sort of data elements of the linked list are you dealing with numeric or string??

---

Does it matter (other than for the comparison statements themselves)?
The image says "int value", so we would think that is the content.

--
Mats

Quote:

---

Originally Posted by matsp

Does it matter (other than for the comparison statements themselves)?
The image says "int value", so we would think that is the content.

--
Mats

---

Well it matters only for the sake of comparison ie the diffference between the element value and the searched value.
Its in the ballpark - the smaller the difference between the two values is.

i can solve ths with one loop and one step each time

but this structure is odd
??

I don't think it matters much - you mean to say that you'd first check if the value difference is > (say) 100, and if so, jump 100 steps forward based on that? If we have a list of three elements, 100, 300, 500, where would your 100 forward be?

--
Mats

i think it will be on null

If we are at the first node we can check what is the number associated with the 100th node. If it is smaller than the number we are looking for then it makes no sense to walk all 100 nodes one by one.

the problem is i cant go back
if i go to the 100th and its too big i am stuck there.

and i got to stick with this structure thing

Yes, I think that's a fair analyzis. So, you don't want to take the 100 forward link unless you KNOW that it works. So check first, if the node at 100 forward is less or equal to what you are looking for. If so, move 100 forward.

--
Mats

we cant check the 100th unless we move there
and we cant make an estimation
it could be

1> 2 > 8 >100000 >100000000000 etc..

and we need to do that by that structure i have been given.

Quote:

---

Originally Posted by matsp

I don't think it matters much - you mean to say that you'd first check if the value difference is > (say) 100, and if so, jump 100 steps forward based on that? If we have a list of three elements, 100, 300, 500, where would your 100 forward be?

--
Mats

---

If there are only 3 elements then one can't skip forward to 100 or even 10 elements for that matter. However this perspective is interesting. Guess I wasn't thinking on those lines ie
skip size == (difference in value between searched value and element value)
I was assuming a conventional heuristic approach. Taking each of the three forks in turn and jumping to the one where the difference is the least.
At best the number of cycles to get to the searched value would be very small and at worst it would be a very expensive simulation of a linear single-step search.

i found the solution but i cant understand the logic of it

and i cant understand the meaning of this kind of line (marked red)

Code:

---

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;
}

---

Quote:

---

Originally Posted by transgalactic2

we cant check the 100th unless we move there
and we cant make an estimation
it could be

1> 2 > 8 >100000 >100000000000 etc..

and we need to do that by that structure i have been given.

---

No need to move to the 100th 10th or next element w/o first checking if searched value >= element value.

Code:

---

if (searched value >= pointer to 100th element->value)
    jump to 100th element
else if (searched value >= pointer to 10th element->value)
    jump to 10th element
else
    jump to next element

---