single link list , binary search

Hi,

I have a single link list which is sorted.

structure of which is like

typedef struct mylist
{
int num;
struct mylist *next;
} MYLIST;

How can I perform binary search on this link list. or should I perform
search on right from the beginning.

Thanks,
Cric

re: single link list , binary search

free2cric@yahoo.com wrote:
[color=blue]
> Hi,
>
> I have a single link list which is sorted.
>
> structure of which is like
>
> typedef struct mylist
> {
> int num;
> struct mylist *next;
> } MYLIST;
>
> How can I perform binary search on this link list. or should I perform
> search on right from the beginning.[/color]

Not really a C question (probably better asked in comp.programming),
but:

<OT>
Efficient binary search requires that you can quickly access any element
(usually by its index), so it's more naturally suited to arrays. If,
however, you're forced to use linked list (and you say it's sorted),
yuo have two ways of approaching this. One is to copy the whole list
into an array and then perform binary search there (not memory
efficient). The other would be to keep everything in the linked list,
and traverse it from the beginning to the required element whenever you
need to test one. In terms of speed, I'd expect the first to be
quicker, as you traverse the whole list only once, although copies may
foul this up. The speed of the second approach depends on the list
contents and exactly which element you're after.
</OT>

--
BR, Vladimir

Sometimes I live in the country,
And sometimes I live in town.
And sometimes I have a great notion,
To jump in the river and drown.

re: single link list , binary search

Vladimir S. Oka schrieb:[color=blue]
> free2cric@yahoo.com wrote:
>
>[color=green]
>>Hi,
>>
>>I have a single link list which is sorted.
>>
>>structure of which is like
>>
>>typedef struct mylist
>>{
>> int num;
>> struct mylist *next;
>>} MYLIST;
>>
>>How can I perform binary search on this link list. or should I perform
>>search on right from the beginning.[/color]
>
>
> Not really a C question (probably better asked in comp.programming),
> but:
>
> <OT>
> Efficient binary search requires that you can quickly access any element
> (usually by its index), so it's more naturally suited to arrays. If,
> however, you're forced to use linked list (and you say it's sorted),
> yuo have two ways of approaching this. One is to copy the whole list
> into an array and then perform binary search there (not memory
> efficient).[/color]

Note: If the linked list elements are not negligible in size, then
rather keep an array of pointers to the list elements.
[color=blue]
> The other would be to keep everything in the linked list,
> and traverse it from the beginning to the required element whenever you
> need to test one. In terms of speed, I'd expect the first to be
> quicker, as you traverse the whole list only once, although copies may
> foul this up. The speed of the second approach depends on the list
> contents and exactly which element you're after.
> </OT>[/color]

Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

re: single link list , binary search

free2cric@yahoo.com wrote:[color=blue]
> Hi,
>
> I have a single link list which is sorted.[/color]

<snip>
[color=blue]
> How can I perform binary search on this link list. or should I perform
> search on right from the beginning.[/color]

<OT>
I think keeping a single linked list sorted must be a big overhead. Are
you:

1. Start from first element.
2. Look at next elements value.
3. If insert value is less than next element value, then insert here,
exit.
4. Else move to next node, goto 2.

If yes, then I believe this is O(n). i.e. you're potentially looking at
every element in the list if your insert value is greater than any
value in the list. This is slow.

Searching will also be O(n), you have to look at potentially every
element in the list. I guess you can exit when you know you're past
your value.

If inserting and searching is done often maybe you should consider a
binary tree? You get sorting for free and searching is O(log N).

Hope this helps.
</OT>

re: single link list , binary search

free2cric@yahoo.com wrote:[color=blue]
> Hi,
>
> I have a single link list which is sorted.
>
> structure of which is like
>
> typedef struct mylist
> {
> int num;
> struct mylist *next;
> } MYLIST;
>
> How can I perform binary search on this link list. or should I perform
> search on right from the beginning.[/color]

This question is off-topic here. Try comp.programming.
Off-topic:
The answer is: you can't. You could simulate it by creating a function
to parse the list to a given element and return the element but this is
not a direct access to your elements and the complexity of the
algorithm changes (well, it's a different algorithm altogether). You
could use binary trees and keep the elements sorted. The problem with
binary trees is that if you choose to implement a simple binary tree
you will often run into situations where they are way off-balance,
meaning that searching an element into a tree may require you to parse
every element of the tree much like you would do with your list. If you
decide to use trees then read about AVL trees and red and black trees.

(If you create nodes in a sorted binary tree in this order: 1, 2, 3, 4,
5, 6 using the natural ordering of integers, then you will end up with
something similar to a single linked list.)

--
Ioan - Ciprian Tandau
tandau _at_ freeshell _dot_ org (hope it's not too late)
(... and that it still works...)

re: single link list , binary search

"Carl R. Davies" <nwsgrp1@googlemail.com> wrote in message
news:1141315734.006824.84520@z34g2000cwc.googlegro ups.com...[color=blue]
> free2cric@yahoo.com wrote:[color=green]
> > Hi,
> >
> > I have a single link list which is sorted.[/color]
>
> <snip>
>[color=green]
> > How can I perform binary search on this link list. or should I perform
> > search on right from the beginning.[/color]
>
> <OT>
> I think keeping a single linked list sorted must be a big overhead. Are
> you:
>
> 1. Start from first element.
> 2. Look at next elements value.
> 3. If insert value is less than next element value, then insert here,
> exit.
> 4. Else move to next node, goto 2.
>
> If yes, then I believe this is O(n). i.e. you're potentially looking at
> every element in the list if your insert value is greater than any
> value in the list. This is slow.[/color]

This is insertion sort, and it is O(n^2) when sorting n elements and yes it
is the worst you can get.
[color=blue]
> Searching will also be O(n), you have to look at potentially every
> element in the list. I guess you can exit when you know you're past
> your value.[/color]

O(logn) and no you do not have to look at every element in the list even in
he worst case.
[color=blue]
> </OT>[/color]

re: single link list , binary search

"Carl R. Davies" <nwsgrp1@googlemail.com> wrote in message
news:1141315734.006824.84520@z34g2000cwc.googlegro ups.com...[color=blue]
> free2cric@yahoo.com wrote:[color=green]
> > Hi,
> >
> > I have a single link list which is sorted.[/color]
>
> <snip>
>[color=green]
> > How can I perform binary search on this link list. or should I perform
> > search on right from the beginning.[/color]
>
> <OT>
> If inserting and searching is done often maybe you should consider a
> binary tree? You get sorting for free and searching is O(log N).[/color]

You could get O(n) in the worst case of a degenerate tree that looks like a
list. Trees must be kept weighted.
[color=blue]
> </OT>[/color]

re: single link list , binary search

"stathis gotsis" <stathisgotsis@hotmail.com> writes:[color=blue]
> "Carl R. Davies" <nwsgrp1@googlemail.com> wrote in message
> news:1141315734.006824.84520@z34g2000cwc.googlegro ups.com...[/color]
[...][color=blue][color=green]
>> If yes, then I believe this is O(n). i.e. you're potentially looking at
>> every element in the list if your insert value is greater than any
>> value in the list. This is slow.[/color]
>
> This is insertion sort, and it is O(n^2) when sorting n elements and yes it
> is the worst you can get.[/color]

There are sorting algorithms *much* worse than O(n^2), but as far as I
know only deliberately perverse ones.
[color=blue][color=green]
>> Searching will also be O(n), you have to look at potentially every
>> element in the list. I guess you can exit when you know you're past
>> your value.[/color]
>
> O(logn) and no you do not have to look at every element in the list even in
> he worst case.[/color]

Searching a linked list is O(n); you can't get to any node without
first traversing all the previous nodes. (The number of nodes you
visit will be n/2 on average; that's still O(n), of course.) A binary
search on a sorted array is O(log n).

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

re: single link list , binary search

"Keith Thompson" <kst-u@mib.org> wrote in message
news:lnwtfcqn34.fsf@nuthaus.mib.org...[color=blue]
> "stathis gotsis" <stathisgotsis@hotmail.com> writes:[color=green]
> > This is insertion sort, and it is O(n^2) when sorting n elements and yes[/color][/color]
it[color=blue][color=green]
> > is the worst you can get.[/color]
>
> There are sorting algorithms *much* worse than O(n^2), but as far as I
> know only deliberately perverse ones.[/color]

I was talking about the more common ones who deliberately opt for efficiency
and not the opposite.
[color=blue][color=green][color=darkred]
> >> Searching will also be O(n), you have to look at potentially every
> >> element in the list. I guess you can exit when you know you're past
> >> your value.[/color]
> >
> > O(logn) and no you do not have to look at every element in the list even[/color][/color]
in[color=blue][color=green]
> > the worst case.[/color]
>
> Searching a linked list is O(n); you can't get to any node without
> first traversing all the previous nodes. (The number of nodes you
> visit will be n/2 on average; that's still O(n), of course.) A binary
> search on a sorted array is O(log n).[/color]

You mean that searching a linked list using the linear search is O(n). The
binary search will perform O(log n) comparisons, but we will have the
traversal overhead added to that. For the binary search to be effective one
can create an array of pointers to the list's nodes, which is equivalent to
the sorted array you mentioned.

re: single link list , binary search

"stathis gotsis" <stathisgotsis@hotmail.com> writes:[color=blue]
> "Keith Thompson" <kst-u@mib.org> wrote in message
> news:lnwtfcqn34.fsf@nuthaus.mib.org...[/color]
[...][color=blue][color=green]
>> Searching a linked list is O(n); you can't get to any node without
>> first traversing all the previous nodes. (The number of nodes you
>> visit will be n/2 on average; that's still O(n), of course.) A binary
>> search on a sorted array is O(log n).[/color]
>
> You mean that searching a linked list using the linear search is O(n).[/color]

Of course.
[color=blue]
> The binary search will perform O(log n) comparisons, but we will
> have the traversal overhead added to that. For the binary search to
> be effective one can create an array of pointers to the list's
> nodes, which is equivalent to the sorted array you mentioned.[/color]

You can't do a binary search on a linked list. If you create an array
of pointers, you can do a binary search on the array of pointers. (I
suppose you *could* call that a binary search on the linked list, but
IMHO that would be misleading.)

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

re: single link list , binary search

"Keith Thompson" <kst-u@mib.org> wrote in message
news:lnhd6gqjah.fsf@nuthaus.mib.org...[color=blue]
> "stathis gotsis" <stathisgotsis@hotmail.com> writes:[color=green]
> > You mean that searching a linked list using the linear search is O(n).[/color]
>
> Of course.
>[color=green]
> > The binary search will perform O(log n) comparisons, but we will
> > have the traversal overhead added to that. For the binary search to
> > be effective one can create an array of pointers to the list's
> > nodes, which is equivalent to the sorted array you mentioned.[/color]
>
> You can't do a binary search on a linked list. If you create an array
> of pointers, you can do a binary search on the array of pointers. (I
> suppose you *could* call that a binary search on the linked list, but
> IMHO that would be misleading.)[/color]

Yes, it is rather meaningless to do a binary search on a linked list, that
is why i supposed that the OP would create some other data structure for the
sake of performing a BS which would then be O(log n).