Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Linked list search question

  1. Oct 29, 2008 #1
    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:


    i need to fill them with something in order to make it work like they told
    Last edited: Oct 29, 2008
  2. jcsd
  3. Oct 29, 2008 #2


    User Avatar

    Staff: Mentor

    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?
  4. Oct 29, 2008 #3
    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: Oct 29, 2008
  5. Oct 29, 2008 #4


    User Avatar

    Staff: Mentor

    You are not stuck, you can check value of the other node not leaving current one.
  6. Oct 29, 2008 #5
    how can i check the value of the other node without leaving the current one?
  7. Oct 29, 2008 #6


    User Avatar

    Staff: Mentor


    You are on your own now.
  8. Oct 29, 2008 #7
    I was thinking about binary search algorithm (log(n)).

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

    once you are in less than 10 range. make 1-1 jumps
  9. Oct 29, 2008 #8
    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 (Text):

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

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

    [COLOR="Red"]while (head->next100 &&  head->next100->value<=key)[/COLOR]

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

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

    if (head->value==key) return head;
    return null;

  10. Oct 29, 2008 #9
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook