Reverse search in a singly-linked list

Discussion in 'C Programming' started by RAJASEKHAR KONDABALA, Dec 24, 2003.

  1. Hi,

    Does anybody know what the fastest way is to "search for a value in a
    singly-linked list from its tail" as oposed to its head?

    I am talking about a non-circular singly-linked list, i.e., head and tail
    are not connected.

    Of course, recursive function aproach to traverse the list is one way. But,
    depending upon the list size, it could overrun the stack pretty fast.

    -sekhar
     
    RAJASEKHAR KONDABALA, Dec 24, 2003
    #1
    1. Advertising

  2. RAJASEKHAR KONDABALA

    Derk Gwen Guest

    # Of course, recursive function aproach to traverse the list is one way. But,
    # depending upon the list size, it could overrun the stack pretty fast.

    Your stack is too small.

    If you want an iterative solution, reverse the list, search, reverse it again.
    The time is linear in the size of the list, which is the same for searching
    an unsorted set.

    #define List(Type,eq) \
    typedef struct List##Type {Type value; struct List##Type link;} List##Type; \
    int searchList##Type(List##Type *list,Type value) { \
    int i; List##Type *p; for (i=0,p=list; p; p=p->link,i++) \
    if (eq(p->value,value)) return i; \
    return -1;} \
    List##Type *reverseList##Type(List##Type list) { \
    List##Type *p,*c,*n; for (p=0,c=list; c; p=c,c=n) \
    {n = c->link; c->link = p;} \
    return p;} \
    int reversesearchList##Type(List##Type *list,Type value) { \
    List##Type *r = reverseList##Type(list); \
    int n = searchList##Type(r,Type value);
    reverseList##Type(r); \
    return n;}

    --
    Derk Gwen http://derkgwen.250free.com/html/index.html
    What kind of convenience store do you run here?
     
    Derk Gwen, Dec 24, 2003
    #2
    1. Advertising

  3. On Tue, 23 Dec 2003 21:24:38 -0500, RAJASEKHAR KONDABALA wrote:

    > Hi,
    >
    > Does anybody know what the fastest way is to "search for a value in a
    > singly-linked list from its tail" as oposed to its head?


    Use a for loop with a function that can retrieve an element from the
    array by index. Of course this will be something like an O(n*log n)
    operation. It would be much faster to convert the list to an array first
    for fast indexing. Better still, don't use a singularly linked list. Use
    a doubly linked list.

    Mike
     
    Michael B Allen, Dec 24, 2003
    #3
  4. RAJASEKHAR KONDABALA <> spoke thus:

    > Does anybody know what the fastest way is to "search for a value in a
    > singly-linked list from its tail" as oposed to its head?


    (The below welcome text was originally written by Ben Pfaff)

    Your question is outside the domain of comp.lang.c, which discusses
    only the standard C programming language, including the standard C
    library. This is a remarkably narrow topic compared to what many
    people expect.

    For your convenience, the list below contains topics that are not
    on-topic for comp.lang.c, and suggests newsgroups for you to explore
    if you have questions about these topics. Please do observe proper
    netiquette before posting to any of these newsgroups. In particular,
    you should read the group's charter and FAQ, if any (FAQs are
    available from www.faqs.org and other sources). If those fail to
    answer your question then you should browse through at least two weeks
    of recent articles to make sure that your question has not already
    been answered.

    * OS-specific questions, such as how to clear the screen,
    access the network, list the files in a directory, or read
    "piped" output from a subprocess. These questions should be
    directed to OS-specific newsgroups, such as
    comp.os.ms-windows.programmer.misc, comp.unix.programmer, or
    comp.os.linux.development.apps.

    * Compiler-specific questions, such as installation issues and
    locations of header files. Ask about these in
    compiler-specific newsgroups, such as gnu.gcc.help or
    comp.os.ms-windows.programmer.misc. Questions about writing
    compilers are appropriate in comp.compilers.

    * Processor-specific questions, such as questions about
    assembly and machine code. x86 questions are appropriate in
    comp.lang.asm.x86, embedded system processor questions may
    be appropriate in comp.arch.embedded.

    * ABI-specific questions, such as how to interface assembly
    code to C. These questions are both processor- and
    OS-specific and should typically be asked in OS-specific
    newsgroups.

    * Algorithms, except questions about C implementations of
    algorithms. "How do I implement algorithm X in C?" is not a
    question about a C implementation of an algorithm, it is a
    request for source code. Newsgroups comp.programming and
    comp.theory may be appropriate.

    * Making C interoperate with other languages. C has no
    facilities for such interoperation. These questions should
    be directed to system- or compiler-specific newsgroups. C++
    has features for interoperating with C, so consider
    comp.lang.c++ for such questions.

    * The C standard, as opposed to standard C. Questions about
    the C standard are best asked in comp.std.c.

    * C++. Please do not post or cross-post questions about C++
    to comp.lang.c. Ask C++ questions in C++ newsgroups, such
    as comp.lang.c++ or comp.lang.c++.moderated.

    * Test posts. Please test in a newsgroup meant for testing,
    such as alt.test.

    news.groups.questions is a good place to ask about the appropriate
    newsgroup for a given topic.

    --
    Christopher Benson-Manica | I *should* know what I'm talking about - if I
    ataru(at)cyberspace.org | don't, I need to know. Flames welcome.
     
    Christopher Benson-Manica, Dec 24, 2003
    #4
  5. begin followup to RAJASEKHAR KONDABALA:
    > Does anybody know what the fastest way is to "search for a value
    > in a singly-linked list from its tail" as oposed to its head?


    Do regular search from start to end, using a simple iterative loop.
    Constant space complexity, linear time complexity.

    const ListElem* find_last_occurence(const ListElem* first, int key)
    {
    const ListElem* result = 0;

    while(first != 0)
    {
    if (first->key == key)
    result = first;
    first = first->next;
    }

    return result;
    }

    --
    Für Google, Tux und GPL!
     
    Alexander Bartolich, Dec 24, 2003
    #5
  6. [OT] Re: Reverse search in a singly-linked list

    RAJASEKHAR KONDABALA wrote:
    > Hi,
    >
    > Does anybody know what the fastest way is to "search for a value in a
    > singly-linked list from its tail" as oposed to its head?
    >
    > I am talking about a non-circular singly-linked list, i.e., head and tail
    > are not connected.
    >

    Given the usual definitions of the terms "singly-linked list" and
    "tail", I'd be surprised that you could find any element in the list
    besides the tail element itself if you are starting your search from the
    tail. I must be missing something...

    --
    Bertrand Mollinier Toublet
    "The open-source movement is a communist affront to capitalism and
    should not be allowed to interfere in the profitable business of
    proprietary software" -- SCO on the Linux community.
     
    Bertrand Mollinier Toublet, Dec 24, 2003
    #6
  7. RAJASEKHAR KONDABALA

    CBFalconer Guest

    RAJASEKHAR KONDABALA wrote:
    >
    > Does anybody know what the fastest way is to "search for a value
    > in a singly-linked list from its tail" as oposed to its head?
    >
    > I am talking about a non-circular singly-linked list, i.e., head
    > and tail are not connected.
    >
    > Of course, recursive function aproach to traverse the list is
    > one way. But, depending upon the list size, it could overrun the
    > stack pretty fast.


    Reverse the list, search from the head, reverse the list again (if
    needed). Reversal takes n extremely simple operations, search
    takes (on average) n/2 fairly complex operations. Pays off if
    more than one search from tail is needed.

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Dec 27, 2003
    #7
  8. RAJASEKHAR KONDABALA

    xarax Guest

    "CBFalconer" <> wrote in message
    news:...
    > RAJASEKHAR KONDABALA wrote:
    > >
    > > Does anybody know what the fastest way is to "search for a value
    > > in a singly-linked list from its tail" as oposed to its head?
    > >
    > > I am talking about a non-circular singly-linked list, i.e., head
    > > and tail are not connected.
    > >
    > > Of course, recursive function aproach to traverse the list is
    > > one way. But, depending upon the list size, it could overrun the
    > > stack pretty fast.

    >
    > Reverse the list, search from the head, reverse the list again (if
    > needed). Reversal takes n extremely simple operations, search
    > takes (on average) n/2 fairly complex operations. Pays off if
    > more than one search from tail is needed.


    Too much work. Just walk the list from head to tail
    and each time you find a node that "matches" what
    you're looking for, stuff the node pointer into a
    variable (initialized to NULL, of course). At the
    end of the walk, the variable will have the address
    of the last node that matched. No need to re-order
    the list, because you would have to walk the list
    anyway, so just look the node with a single walk.
     
    xarax, Dec 27, 2003
    #8
  9. xarax <> wrote:
    > "CBFalconer" <> wrote in message
    >> Reverse the list, search from the head, reverse the list again (if
    >> needed). Reversal takes n extremely simple operations, search takes
    >> (on average) n/2 fairly complex operations. Pays off if more than
    >> one search from tail is needed.

    >
    > Too much work. Just walk the list from head to tail and each time you
    > find a node that "matches" what you're looking for, stuff the node
    > pointer into a variable (initialized to NULL, of course). At the end
    > of the walk, the variable will have the address of the last node that
    > matched. No need to re-order the list, because you would have to walk
    > the list anyway, so just look the node with a single walk.


    As CBFalconer said, reversing the list is probably going to be cheaper,
    unless your test condition is extremely cheap. If we are comparing
    strings, for example, reversing the list will almost certainly be
    faster. Walking the list once we're forced to do N string compares for a
    list with N nodes. If we reverse the list we can get away with N/2 such
    compares on average.

    This makes certain assumptions about the dataset that might not hold
    true of course.

    Stig
    --
    brautaset.org
     
    Stig Brautaset, Dec 28, 2003
    #9
  10. begin followup to Stig Brautaset:
    > If we are comparing strings, for example, reversing the list will
    > almost certainly be faster.


    Nope.

    > Walking the list once we're forced to do N string compares for a
    > list with N nodes.


    That's for walking an unsorted list.

    > If we reverse the list we can get away with N/2 such compares on
    > average.


    Only if the list was sorted before.

    Anyway, if it takes exactly N/2 comparisons to find the first
    occurence of the mystical average element in a sorted list,
    than search the last occurence of that element takes N/2 + M
    comparisons, where M ist the number of matches.

    --
    Für Google, Tux und GPL!
     
    Alexander Bartolich, Dec 28, 2003
    #10
  11. RAJASEKHAR KONDABALA

    CBFalconer Guest

    xarax wrote:
    > "CBFalconer" <> wrote in message
    > > RAJASEKHAR KONDABALA wrote:
    > > >
    > > > Does anybody know what the fastest way is to "search for a value
    > > > in a singly-linked list from its tail" as oposed to its head?
    > > >
    > > > I am talking about a non-circular singly-linked list, i.e., head
    > > > and tail are not connected.
    > > >
    > > > Of course, recursive function aproach to traverse the list is
    > > > one way. But, depending upon the list size, it could overrun the
    > > > stack pretty fast.

    > >
    > > Reverse the list, search from the head, reverse the list again (if
    > > needed). Reversal takes n extremely simple operations, search
    > > takes (on average) n/2 fairly complex operations. Pays off if
    > > more than one search from tail is needed. ^^^^^^^^^^^

    > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    >
    > Too much work. Just walk the list from head to tail and each time
    > you find a node that "matches" what you're looking for, stuff the
    > node pointer into a variable (initialized to NULL, of course). At
    > the end of the walk, the variable will have the address of the last
    > node that matched. No need to re-order the list, because you would
    > have to walk the list anyway, so just look the node with a single
    > walk.


    You failed to read the complete paragraph, especially the portion
    underlined above. Note that your method always requires n complex
    operations.

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Dec 28, 2003
    #11
  12. Alexander Bartolich <> wrote:
    > begin followup to Stig Brautaset:
    >> If we are comparing strings, for example, reversing the list will
    >> almost certainly be faster.

    >
    > Nope.


    I believe so, yes, for unsorted lists. Of course, if you are going to
    throw many searches at it you can do worse than sorting the list first.

    >> Walking the list once we're forced to do N string compares for a
    >> list with N nodes.

    >
    > That's for walking an unsorted list.


    True, but whether the list was sorted or unsorted was not specified. I
    assumed an unsorted list (and so did you, afaics, in your previous post
    to the OP ;).

    >> If we reverse the list we can get away with N/2 such compares on
    >> average.

    >
    > Only if the list was sorted before.


    Are you sure? AFAICS you can get away with visiting N/2 nodes on
    average, regardless of whether the list is sorted or not.

    Stig

    --
    brautaset.org
     
    Stig Brautaset, Dec 28, 2003
    #12
  13. begin followup to Stig Brautaset:
    > Are you sure? AFAICS you can get away with visiting N/2 nodes on
    > average, regardless of whether the list is sorted or not.


    On a sorted list you can stop the walk as soon as we find a

    current_node->key > search_key

    On an unsorted list you have look at all nodes, always.

    --
    Für Google, Tux und GPL!
     
    Alexander Bartolich, Dec 28, 2003
    #13
  14. RAJASEKHAR KONDABALA

    CBFalconer Guest

    Alexander Bartolich wrote:
    > begin followup to Stig Brautaset:
    >
    > > Are you sure? AFAICS you can get away with visiting N/2 nodes on
    > > average, regardless of whether the list is sorted or not.

    >
    > On a sorted list you can stop the walk as soon as we find a
    >
    > current_node->key > search_key
    >
    > On an unsorted list you have look at all nodes, always.


    Sorting does not enter into it. The original request was for a
    search from the tail, implying that the result required was the
    value nearest the tail. By reversing the list you have only to
    search until something is found, or nothing is found. Without
    reversal you have to scan the entire list at all times.

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Dec 28, 2003
    #14
  15. RAJASEKHAR KONDABALA

    xarax Guest

    "CBFalconer" <> wrote in message
    news:...
    > xarax wrote:
    > > "CBFalconer" <> wrote in message
    > > > RAJASEKHAR KONDABALA wrote:
    > > > >
    > > > > Does anybody know what the fastest way is to "search for a value
    > > > > in a singly-linked list from its tail" as oposed to its head?
    > > > >
    > > > > I am talking about a non-circular singly-linked list, i.e., head
    > > > > and tail are not connected.
    > > > >
    > > > > Of course, recursive function aproach to traverse the list is
    > > > > one way. But, depending upon the list size, it could overrun the
    > > > > stack pretty fast.
    > > >
    > > > Reverse the list, search from the head, reverse the list again (if
    > > > needed). Reversal takes n extremely simple operations, search
    > > > takes (on average) n/2 fairly complex operations. Pays off if
    > > > more than one search from tail is needed. ^^^^^^^^^^^

    > > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    > >
    > > Too much work. Just walk the list from head to tail and each time
    > > you find a node that "matches" what you're looking for, stuff the
    > > node pointer into a variable (initialized to NULL, of course). At
    > > the end of the walk, the variable will have the address of the last
    > > node that matched. No need to re-order the list, because you would
    > > have to walk the list anyway, so just look the node with a single
    > > walk.

    >
    > You failed to read the complete paragraph, especially the portion
    > underlined above. Note that your method always requires n complex
    > operations.


    I was responding (primarily) to the original question
    was did not specify whether the list was sorted nor
    what the "value" was.

    The underlined text in a responder's post is adding
    an assumption that the "value" requires a non-scalar
    comparison.

    I could also add more requirements, such as the list
    is currently being accessed and modified by multiple
    threads. What's the most efficient way to find the
    matching non-scalar value that is nearest to the end
    of a LIFO singly-linked list being concurrently modified
    by multiple threads? (That's a rhetorical question.)

    Just taking the OP's question at face value, there are
    no hidden "gotcha's", like non-scalar value (increases
    the cost of comparison) or multithreading (cannot change
    the ordering of the list). In that original case, there's
    no reason to reorder the list (twice) to find the last
    matching value.


    --
    ----------------------------
    Jeffrey D. Smith
    Farsight Systems Corporation
    24 BURLINGTON DRIVE
    LONGMONT, CO 80501-6906
    http://www.farsight-systems.com
    z/Debug debugs your Systems/C programs running on IBM z/OS!
    Are ISV upgrade fees too high? Check our custom product development!
     
    xarax, Dec 28, 2003
    #15
  16. RAJASEKHAR KONDABALA

    CBFalconer Guest

    xarax wrote:
    > "CBFalconer" <> wrote in message
    > > xarax wrote:
    > > > "CBFalconer" <> wrote in message
    > > > > RAJASEKHAR KONDABALA wrote:
    > > > > >
    > > > > > Does anybody know what the fastest way is to "search for a value
    > > > > > in a singly-linked list from its tail" as oposed to its head?
    > > > > >
    > > > > > I am talking about a non-circular singly-linked list, i.e., head
    > > > > > and tail are not connected.
    > > > > >
    > > > > > Of course, recursive function aproach to traverse the list is
    > > > > > one way. But, depending upon the list size, it could overrun the
    > > > > > stack pretty fast.
    > > > >
    > > > > Reverse the list, search from the head, reverse the list again (if
    > > > > needed). Reversal takes n extremely simple operations, search
    > > > > takes (on average) n/2 fairly complex operations. Pays off if
    > > > > more than one search from tail is needed. ^^^^^^^^^^^
    > > > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    > > >
    > > > Too much work. Just walk the list from head to tail and each time
    > > > you find a node that "matches" what you're looking for, stuff the
    > > > node pointer into a variable (initialized to NULL, of course). At
    > > > the end of the walk, the variable will have the address of the last
    > > > node that matched. No need to re-order the list, because you would
    > > > have to walk the list anyway, so just look the node with a single
    > > > walk.

    > >
    > > You failed to read the complete paragraph, especially the portion
    > > underlined above. Note that your method always requires n complex
    > > operations.

    >
    > I was responding (primarily) to the original question
    > was did not specify whether the list was sorted nor
    > what the "value" was.
    >
    > The underlined text in a responder's post is adding
    > an assumption that the "value" requires a non-scalar
    > comparison.


    No it doesn't. It assumes that finding an item involves a
    comparison. List reversal does not, which is why it is so quick
    and easy.
    >
    > I could also add more requirements, such as the list
    > is currently being accessed and modified by multiple
    > threads. What's the most efficient way to find the
    > matching non-scalar value that is nearest to the end
    > of a LIFO singly-linked list being concurrently modified
    > by multiple threads? (That's a rhetorical question.)


    And entirely off-topic in c.l.c. C has no threads, nor
    concurrency constructs.

    >
    > Just taking the OP's question at face value, there are
    > no hidden "gotcha's", like non-scalar value (increases
    > the cost of comparison) or multithreading (cannot change
    > the ordering of the list). In that original case, there's
    > no reason to reorder the list (twice) to find the last
    > matching value.


    It only needs one reversal. The second is only if the original
    list must be restored. Having put a singly linked list reversal
    routine in your pocket, you will find it has many uses. It is
    also simple and understandable, so you can build things quickly
    out of proven components, WAPO (while avoiding premature
    optimization).

    Pseudo code:

    list = revlist(list);
    lastoftype1 = searchfirst(list, type1);
    lastoftype2 = searchfirst(list, type2);
    list = revlist(list); /* if needed */

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Dec 28, 2003
    #16
  17. begin followup to CBFalconer:
    > Sorting does not enter into it. The original request was for a
    > search from the tail, implying that the result required was the
    > value nearest the tail. By reversing the list you have only to
    > search until something is found, or nothing is found. Without
    > reversal you have to scan the entire list at all times.


    Alright. Let's organize this and take all fun out of it.
    Actually there are two independent aspects, giving four cases.
    A search for the first occurrence of the average element:

    successful failed
    sorted | n/2 n/2
    unsorted | n/2 n

    N ist the number of list items. Result of the lookup is the required
    number of comparisons. Now the search for the _last_ occurrence:

    successful failed
    sorted | n/2 + m n/2
    unsorted | n n

    Where m is the number of occurences.

    So sorting does indeed enter the story. For a sorted list the
    performance improvement of reversing the list upfront is minimal.

    And on the other hand reversion is a probably a rather expensive
    operation. You walk all elements of the list and insert them into
    new list. This requires changing the next-pointer of every element,
    as opposed to just reading the key element for comparison.

    And things get worse if you need the keep the original, unreversed
    list for later on. There is the issue of concurrency - you can have
    many simultaneous readers, but only one writer. And of course the
    magic spell of all performance discussions: invalidated cache lines.

    --
    Für Google, Tux und GPL!
     
    Alexander Bartolich, Dec 29, 2003
    #17
  18. RAJASEKHAR KONDABALA

    CBFalconer Guest

    Alexander Bartolich wrote:
    > begin followup to CBFalconer:
    >
    > > Sorting does not enter into it. The original request was for a
    > > search from the tail, implying that the result required was the
    > > value nearest the tail. By reversing the list you have only to
    > > search until something is found, or nothing is found. Without
    > > reversal you have to scan the entire list at all times.

    >
    > Alright. Let's organize this and take all fun out of it.


    .... snip stuff not germane to the problem ...

    The fact that the OP wants the value nearest the tail implies both
    an unsorted list and a list with possible multiple entries for any
    given key.

    --
    Chuck F () ()
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net> USE worldnet address!
     
    CBFalconer, Dec 29, 2003
    #18
  19. RAJASEKHAR KONDABALA

    pete Guest

    CBFalconer wrote:
    >
    > xarax wrote:
    > > "CBFalconer" <> wrote in message
    > > > xarax wrote:
    > > > > "CBFalconer" <> wrote in message
    > > > > > RAJASEKHAR KONDABALA wrote:
    > > > > > >
    > > > > > > Does anybody know what the fastest way is
    > > > > > > to "search for a value
    > > > > > > in a singly-linked list from its tail"
    > > > > > > as oposed to its head?
    > > > > > >
    > > > > > > I am talking about a non-circular singly-linked list,
    > > > > > > i.e., head and tail are not connected.
    > > > > > >
    > > > > > > Of course, recursive function aproach to
    > > > > > > traverse the list is one way.
    > > > > > > But, depending upon the list size,
    > > > > > > it could overrun the stack pretty fast.
    > > > > >
    > > > > > Reverse the list, search from the head,
    > > > > > reverse the list again (if needed).
    > > > > > Reversal takes n extremely simple operations, search
    > > > > > takes (on average) n/2 fairly complex operations.
    > > > > > Pays off if more than one search from tail is needed.
    > > > > > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    > > > > Too much work.
    > > > > Just walk the list from head to tail and each time
    > > > > you find a node that "matches" what you're looking for,
    > > > > stuff the node pointer into a variable
    > > > > (initialized to NULL, of course).
    > > > > At the end of the walk,
    > > > > the variable will have the address of the last
    > > > > node that matched. No need to re-order the list,
    > > > > because you would have to walk the list anyway,
    > > > > so just look the node with a single walk.
    > > >
    > > > You failed to read the complete paragraph, especially the portion
    > > > underlined above. Note that your method always requires n complex
    > > > operations.

    > >
    > > I was responding (primarily) to the original question
    > > was did not specify whether the list was sorted nor
    > > what the "value" was.
    > >
    > > The underlined text in a responder's post is adding
    > > an assumption that the "value" requires a non-scalar
    > > comparison.

    >
    > No it doesn't. It assumes that finding an item involves a
    > comparison. List reversal does not, which is why it is so quick
    > and easy.
    > >
    > > I could also add more requirements, such as the list
    > > is currently being accessed and modified by multiple
    > > threads. What's the most efficient way to find the
    > > matching non-scalar value that is nearest to the end
    > > of a LIFO singly-linked list being concurrently modified
    > > by multiple threads? (That's a rhetorical question.)

    >
    > And entirely off-topic in c.l.c. C has no threads, nor
    > concurrency constructs.


    I think this is a comp.programming topic, but I don't know.

    You seem to be viewing this problem
    from two differents points of view:
    1 It's a speed problem.
    2 It's a last occurance search.

    The first option occured to me.
    It implies that the comparison takes considerable time,
    and/or that the searched for node,
    is known to be near the end of the list.
    After further consideration,
    I think that OP's interest in a last occurance search,
    might be more likely.

    I don't think that a sorted list was implied.
    In either case, reversing the list first,
    would be the simplest thing.

    Suppose the last occurance, was the first node.
    One way:
    You reverse the list, search it's length, find the node,
    and maybe reverse it back.
    The other way, you search the length of the list,
    keeping track of your first node.

    So, the first way, you have the same operational intensity
    as the second way, plus one or two list reversals.

    Suppose the last occurance, was the last node.
    One way:
    You reverse the list, search one node and boom, you're done,
    and maybe reverse it back.
    The other way, you search the length of the list.

    I like the list reversal, because it's simple,
    and list reversal isn't too big of a deal,
    as list operations go.

    In order to know which way is faster,
    you would have to know how time consuming the comparison is
    and where the node is expected to be found.
    If the searched for node,
    is expected to be randomly located in the list,
    then there will be on average,
    half as many node comparisons using the reversal method,
    but a lot more pointer assignments.

    If the data is an int type,
    and the comparisons are just "((a) > (b))" macros,
    instead of functions, then not reversing might be faster.

    Without knowing more, the reversal first way, appeals to me.

    --
    pete
     
    pete, Dec 29, 2003
    #19
  20. "pete" <> wrote in message
    news:...
    > CBFalconer wrote:
    > >
    > > xarax wrote:
    > > > "CBFalconer" <> wrote in message
    > > > > xarax wrote:
    > > > > > "CBFalconer" <> wrote in message
    > > > > > > RAJASEKHAR KONDABALA wrote:
    > > > > > > >
    > > > > > > > Does anybody know what the fastest way is
    > > > > > > > to "search for a value
    > > > > > > > in a singly-linked list from its tail"
    > > > > > > > as oposed to its head?
    > > > > > > >
    > > > > > > > I am talking about a non-circular singly-linked list,
    > > > > > > > i.e., head and tail are not connected.
    > > > > > > >
    > > > > > > > Of course, recursive function aproach to
    > > > > > > > traverse the list is one way.
    > > > > > > > But, depending upon the list size,
    > > > > > > > it could overrun the stack pretty fast.
    > > > > > >
    > > > > > > Reverse the list, search from the head,
    > > > > > > reverse the list again (if needed).
    > > > > > > Reversal takes n extremely simple operations, search
    > > > > > > takes (on average) n/2 fairly complex operations.
    > > > > > > Pays off if more than one search from tail is needed.
    > > > > > > ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    > > > > > Too much work.
    > > > > > Just walk the list from head to tail and each time
    > > > > > you find a node that "matches" what you're looking for,
    > > > > > stuff the node pointer into a variable
    > > > > > (initialized to NULL, of course).
    > > > > > At the end of the walk,
    > > > > > the variable will have the address of the last
    > > > > > node that matched. No need to re-order the list,
    > > > > > because you would have to walk the list anyway,
    > > > > > so just look the node with a single walk.
    > > > >
    > > > > You failed to read the complete paragraph, especially the portion
    > > > > underlined above. Note that your method always requires n complex
    > > > > operations.
    > > >
    > > > I was responding (primarily) to the original question
    > > > was did not specify whether the list was sorted nor
    > > > what the "value" was.
    > > >
    > > > The underlined text in a responder's post is adding
    > > > an assumption that the "value" requires a non-scalar
    > > > comparison.

    > >
    > > No it doesn't. It assumes that finding an item involves a
    > > comparison. List reversal does not, which is why it is so quick
    > > and easy.
    > > >
    > > > I could also add more requirements, such as the list
    > > > is currently being accessed and modified by multiple
    > > > threads. What's the most efficient way to find the
    > > > matching non-scalar value that is nearest to the end
    > > > of a LIFO singly-linked list being concurrently modified
    > > > by multiple threads? (That's a rhetorical question.)

    > >
    > > And entirely off-topic in c.l.c. C has no threads, nor
    > > concurrency constructs.

    >
    > I think this is a comp.programming topic, but I don't know.
    >
    > You seem to be viewing this problem
    > from two differents points of view:
    > 1 It's a speed problem.
    > 2 It's a last occurance search.
    >
    > The first option occured to me.
    > It implies that the comparison takes considerable time,
    > and/or that the searched for node,
    > is known to be near the end of the list.
    > After further consideration,
    > I think that OP's interest in a last occurance search,
    > might be more likely.
    >
    > I don't think that a sorted list was implied.
    > In either case, reversing the list first,
    > would be the simplest thing.
    >
    > Suppose the last occurance, was the first node.
    > One way:
    > You reverse the list, search it's length, find the node,
    > and maybe reverse it back.
    > The other way, you search the length of the list,
    > keeping track of your first node.
    >
    > So, the first way, you have the same operational intensity
    > as the second way, plus one or two list reversals.
    >
    > Suppose the last occurance, was the last node.
    > One way:
    > You reverse the list, search one node and boom, you're done,
    > and maybe reverse it back.
    > The other way, you search the length of the list.
    >
    > I like the list reversal, because it's simple,
    > and list reversal isn't too big of a deal,
    > as list operations go.
    >
    > In order to know which way is faster,
    > you would have to know how time consuming the comparison is
    > and where the node is expected to be found.
    > If the searched for node,
    > is expected to be randomly located in the list,
    > then there will be on average,
    > half as many node comparisons using the reversal method,
    > but a lot more pointer assignments.
    >
    > If the data is an int type,
    > and the comparisons are just "((a) > (b))" macros,
    > instead of functions, then not reversing might be faster.
    >
    > Without knowing more, the reversal first way, appeals to me.
    >
    > --
    > pete


    Both solutions require that you touch every node in the list, so they're not
    exactly memory friendly. The advantage of reversing the list is that
    subsequent searches can drop out early when a matching value is found. Of
    course, if the list doesn't contain the value you're looking for, you'll end
    up visiting every node anyway.

    My take on this is that if you find you need to search a linked list from
    its tail, you've got your design wrong. The list should be chained the other
    way, or it should be a doubly linked list. Get the design right and the
    question just goes away.

    One other point - scanning a linked list is inherently inefficient; if speed
    is a factor some other data structure - a (balanced) tree, or hash table for
    instance - would be favourite. If you;re stuck with the list, you could
    perhaps add a search cache based on one of those techniques.

    If you're really really stuck with a list (because for instance this is an
    assignment question) the answer is 'it depends'...

    --
    Roger
     
    Roger Willcocks, Dec 29, 2003
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Patrick McCourt

    Stack & Singly Linked List Data Structures

    Patrick McCourt, May 24, 2004, in forum: Java
    Replies:
    2
    Views:
    952
    Kenneth P. Turvey
    May 24, 2004
  2. HS-MOON
    Replies:
    4
    Views:
    620
    Method Man
    Sep 24, 2004
  3. CR

    AlphaSort for singly linked list

    CR, Dec 15, 2003, in forum: C Programming
    Replies:
    1
    Views:
    525
    CBFalconer
    Dec 15, 2003
  4. Anando

    pruning a linear singly linked list

    Anando, Apr 23, 2006, in forum: C Programming
    Replies:
    59
    Views:
    1,281
    Richard Bos
    Apr 28, 2006
  5. Raj
    Replies:
    13
    Views:
    1,651
Loading...

Share This Page