473,890 Members | 1,397 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Reverse search in a singly-linked list

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
Nov 14 '05
19 13583
xarax wrote:
"CBFalconer " <cb********@yah oo.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.

--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!
Nov 14 '05 #11
Alexander Bartolich <al************ *****@gmx.at> 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
Nov 14 '05 #12
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!
Nov 14 '05 #13
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 (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!
Nov 14 '05 #14
"CBFalconer " <cb********@yah oo.com> wrote in message
news:3F******** *******@yahoo.c om...
xarax wrote:
"CBFalconer " <cb********@yah oo.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.

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!
Nov 14 '05 #15
xarax wrote:
"CBFalconer " <cb********@yah oo.com> wrote in message
xarax wrote:
"CBFalconer " <cb********@yah oo.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.

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(lis t, type1);
lastoftype2 = searchfirst(lis t, type2);
list = revlist(list); /* if needed */

--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!
Nov 14 '05 #16
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!
Nov 14 '05 #17
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 (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!
Nov 14 '05 #18
CBFalconer wrote:

xarax wrote:
"CBFalconer " <cb********@yah oo.com> wrote in message
xarax wrote:
> "CBFalconer " <cb********@yah oo.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.programmin g 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
Nov 14 '05 #19

"pete" <pf*****@mindsp ring.com> wrote in message
news:3F******** ***@mindspring. com...
CBFalconer wrote:

xarax wrote:
"CBFalconer " <cb********@yah oo.com> wrote in message
> xarax wrote:
> > "CBFalconer " <cb********@yah oo.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.programmin g 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
Nov 14 '05 #20

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

9
10366
by: Ron Adam | last post by:
Is it possible to match a string to regular expression pattern instead of the other way around? For example, instead of finding a match within a string, I want to find out, (pass or fail), if a string is a partial match to an re. Given an re of 'abcd and a bunch of other stuff' This is what i'm looking for:
5
7438
by: Robert Brown | last post by:
I have researched newsgroups and the web very thoroughly and unsuccessfully for a solution to what I believe is a very common problem. I know it's easy to do wildcard match against data in DB (using LIKE and "%" and "?"). But is it possible to match a concrete string against a database of wildcarded data? ("%" and LIKE do not work). For example: CREATE TABLE blacklist (
9
3981
by: Robert Brown | last post by:
If I use _reverse_ wildcard search will it always result in a table scan? Is it possible to get the DB (Oracle or SQL server) to use indexes when doing reverse wildcard match? let's say I have: table email_address (id int, email varchar) with the following entries
6
6773
by: 3strands | last post by:
Hi! I am writing a C++ program for a school project. It's a project and I could do it without this particualr feature, it's just it would be better if I could find out one thing: I'm making a simple game to simulate the rabbit vs. tortoise race. I need to print a race track on the screen like so: ###############R######
3
1716
by: Paul Aspinall | last post by:
I have been developing apps in C#... Until recently, I was not concerned about the compilation to IL step, which many people had been concerned about. However, having spent a few hours using ILDASM and Refelector, I am very concerned about the ease at which my code can be reverse engineered.... This does not really seem like a very good 'feature' for marketing commercial products on the platform.
15
5095
by: Fady Anwar | last post by:
Hi while browsing the net i noticed that there is sites publishing some software that claim that it can decompile .net applications i didn't bleave it in fact but after trying it i was surprised that i could retrieve my code from my applications after i compile it so i need to know to prevent this from happening to my applications Thanx in advance
2
1770
by: David T. Ashley | last post by:
Hi Guys, Given an IP address, what is the easiest way to reverse-DNS and get a name, if one exists? Thanks, Dave.
20
19823
by: mike7411 | last post by:
Is there any easy way to reverse the order of the bits in a byte in C++? (i.e. 00000001 becomes 10000000)
4
6849
by: ranjanmg1 | last post by:
I have a unsigned char.. i need to reverse it.. what the easiest way to do it?? i dont want to tap each bit save and restore etc etc.... Is it possible to perform some bitwise operation which will give the reversed char. e.g., unsigned char x = 0x8A am expecting an output after reversal x = 0x51
1
1933
by: SamudraSri | last post by:
hi everybody i am working wamp since 4+ years. i have a requirement where in i need to search for the record that matches some keywords using fulltext search. tables: temp1(id,keywords,searchin,matchwords); temp2(id,keywords,title)
0
9826
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
11236
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10830
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
10468
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
9641
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
5855
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
6061
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
4682
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
3
3283
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.