Thread: linked list search question..

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    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
    Last edited by transgalactic2; 10-29-2008 at 02:08 PM.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    What sort of data elements of the linked list are you dealing with numeric or string??

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by itCbitC View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by matsp View Post
    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.

  6. #6
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i can solve ths with one loop and one step each time

    but this structure is odd
    ??

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    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
    Last edited by transgalactic2; 10-29-2008 at 03:19 PM.

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    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.

  11. #11
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by matsp View Post
    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.

  12. #12
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    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;
    }

  13. #13
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,059
    Quote Originally Posted by transgalactic2 View Post
    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
    Last edited by itCbitC; 10-29-2008 at 04:55 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Need help sorting a linked list. Beginner
    By scarlet00014 in forum C Programming
    Replies: 1
    Last Post: 09-27-2008, 06:16 PM
  3. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  4. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  5. linked list inside array of structs- Syntax question
    By rasmith1955 in forum C Programming
    Replies: 14
    Last Post: 02-28-2005, 05:16 PM