Re: Reverse search in a singly-linked list

From: pete (pfiland_at_mindspring.com)
Date: 12/29/03 

Date: Mon, 29 Dec 2003 12:54:27 GMT

CBFalconer wrote:
>
> xarax wrote:
> > "CBFalconer" <cbfalconer@yahoo.com> wrote in message
> > > xarax wrote:
> > > > "CBFalconer" <cbfalconer@yahoo.com> 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
Quantcast