Using a link list over an array.

[pereges]

Re: Using a link list over an array.

btw since i saw it pete's code, isn't the static return type of a
function supposed to make it private ? What is the advantage of using
it ? Will it restrict the amount of code that is included in other
files ?

[pereges]

Re: Using a link list over an array.

btw since i saw it pete's code, isn't the static declaration of a
function supposed to make it private ? What is the advantage of using
it ? Will it restrict the amount of code that is included in other
files ?

[pete]

Re: Using a link list over an array.

pereges wrote:

btw since i saw it pete's code, isn't the static return type of a
function supposed to make it private ? What is the advantage of using
it ? Will it restrict the amount of code that is included in other
files ?

It's because I grabbed it out a small library
where only six of the list functions are public.

I prefer my public list functions to treat NULL
as a pointer to a list of zero length.
My static list functions don't do that.
They are written only to be called
from the public functions
which don't generate calls with NULL arguments.

merge_lists, which is one of the static functions
that you've seen posted as one of the helper functions
for list_sort, isn't made to handle a zero length list.
This is its public interface:

list_type *list_merge(lis t_type *head, list_type *tail,
int (*compar)(const list_type *, const list_type *))
{
if (tail != NULL) {
if (head != NULL) {
head = merge_lists(hea d, tail, compar);
} else {
head = tail;
}
}
return head;
}

http://www.mindspring.com/~pfilandr/C/lists_and_files/list_lib.h

http://www.mindspring.com/~pfilandr/C/lists_and_files/list_lib.c

--
pete

[CBFalconer]

Re: Using a link list over an array.

pereges wrote:

>
btw since i saw it pete's code, isn't the static return type of a
function supposed to make it private ? What is the advantage of
using it ? Will it restrict the amount of code that is included
in other files ?

That 'static' applies to the function, not the returned type. It
hides the function from any other source file, although it can be
passed out as a function pointer.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.

[Richard Tobin]

Re: Using a link list over an array.

In article <486B8589.71AD0 5D9@yahoo.com>,
CBFalconer <cbfalconer@mai neline.netwrote :

>btw since i saw it pete's code, isn't the static return type of a
>function supposed to make it private ? What is the advantage of
>using it ? Will it restrict the amount of code that is included
>in other files ?

>That 'static' applies to the function, not the returned type.

More precisely, it refers to the *name* of the function. That's
why:

... it can be passed out as a function pointer.

-- Richard
--
Please remember to mention me / in tapes you leave behind.

[Herbert Rosenau]

Re: Using a link list over an array.

On Mon, 30 Jun 2008 19:35:11 UTC, pereges <Broli00@gmail. comwrote:

>
Is it easier to sort link lists as opposed to arrays ?? In one
implementation of quick sort applied on link lists, I saw that even
accessing a single Nth node required n-1 passes.

When you have to sort an array you have to move complete array members
around. This is time intensive at all.

Sorting lists - whenever this can not done easy while sort while
inserting - is nothing than moving pointers to elements around. Lots
of less work.

Exchanging 2 array members needs
- copy one array member out of its place
- copy the other member on its new place
- copy the other member on the place the other was

Exchanging 2 list elements is is easy done by moving pointers to them
around. Not a single list member has to be moved at all.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2R Deutsch ist da!

[Barry Schwarz]

Re: Using a link list over an array.

On Thu, 3 Jul 2008 05:57:16 +0000 (UTC), "Herbert Rosenau"
<os2guy@pc-rosenau.dewrote :

>On Mon, 30 Jun 2008 19:35:11 UTC, pereges <Broli00@gmail. comwrote:
>

>>
>Is it easier to sort link lists as opposed to arrays ?? In one
>implementati on of quick sort applied on link lists, I saw that even
>accessing a single Nth node required n-1 passes.

>
>When you have to sort an array you have to move complete array members
>around. This is time intensive at all.
>
>Sorting lists - whenever this can not done easy while sort while
>inserting - is nothing than moving pointers to elements around. Lots
>of less work.
>
>Exchanging 2 array members needs
>- copy one array member out of its place
>- copy the other member on its new place
>- copy the other member on the place the other was
>
>Exchanging 2 list elements is is easy done by moving pointers to them
>around. Not a single list member has to be moved at all.

Let node a point to node b point to node c point to node d. Let's
swap b and c. Let's make it easy and assume we know it is a that
points to b (otherwise we have to spend time finding it).
Copy a.next to a temp.
Copy b.next to a.next
Copy c.next to b.next
Copy the temp to c.next

Unless the array elements are aggregates, arrays look faster.



Remove del for email