Linked list search question

  • #1
1,395
0

Main Question or Discussion Point

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
 
Last edited:

Answers and Replies

  • #2
Borek
Mentor
28,473
2,871
If you are at the first node you can check what is the number associated with the 100th 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?
 
  • #3
1,395
0
but i cant 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
 
Last edited:
  • #4
Borek
Mentor
28,473
2,871
You are not stuck, you can check value of the other node not leaving current one.
 
  • #5
1,395
0
how can i check the value of the other node without leaving the current one?
 
  • #6
Borek
Mentor
28,473
2,871
head->next100->value

You are on your own now.
 
  • #7
378
2
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
 
  • #8
1,395
0
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;

[COLOR="Red"]while (head->next100 &&  head->next100->value<=key)[/COLOR]
         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;
}
 
  • #9
378
2
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
 

Related Threads on Linked list search question

Replies
9
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
12
Views
2K
  • Last Post
Replies
9
Views
4K
Replies
3
Views
616
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
20
Views
3K
  • Last Post
Replies
1
Views
2K
Top