Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Reverse search in a singly-linked list (http://www.velocityreviews.com/forums/t316693-reverse-search-in-a-singly-linked-list.html)

RAJASEKHAR KONDABALA 12-24-2003 02:24 AM

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



Derk Gwen 12-24-2003 03:10 AM

Re: Reverse search in a singly-linked list
 
# 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?

Michael B Allen 12-24-2003 06:04 AM

Re: Reverse search in a singly-linked list
 
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

Christopher Benson-Manica 12-24-2003 02:22 PM

Re: Reverse search in a singly-linked list
 
RAJASEKHAR KONDABALA <sekharol@verizon.net> 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.

Alexander Bartolich 12-24-2003 02:30 PM

Re: Reverse search in a singly-linked list
 
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!

Bertrand Mollinier Toublet 12-24-2003 03:46 PM

[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.

CBFalconer 12-27-2003 07:02 AM

Re: Reverse search in a singly-linked list
 
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 (cbfalconer@yahoo.com) (cbfalconer@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!



xarax 12-27-2003 04:26 PM

Re: Reverse search in a singly-linked list
 
"CBFalconer" <cbfalconer@yahoo.com> wrote in message
news:3FED258E.CFF60140@yahoo.com...
> 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.



Stig Brautaset 12-28-2003 12:32 AM

Re: Reverse search in a singly-linked list
 
xarax <xarax@email.com> wrote:
> "CBFalconer" <cbfalconer@yahoo.com> 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

Alexander Bartolich 12-28-2003 12:52 AM

Re: Reverse search in a singly-linked list
 
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!


All times are GMT. The time now is 02:46 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.