Linked lists and pointers

[paudirac]

Hi,

I need to maintain N linked lists where N is determined at runtime.
The linked lists are defined as follows,

struct linked_list {
int data;
struct linked_list next;
}

I thought of two arrays of pointers
struct linked_list **first;
struct linked_list **last;
in order to acces the linked_lists.

I have the following methods,

void
init_lists(cons t int N)
{
first = (struct linked_particle **)calloc(N, sizeof(struct
linked_particle *));
last = (struct linked_particle **)malloc(N * sizeof(struct
linked_particle *));

int i;
for (i = 0; i < N; i++) {
struct linked_particle *nova =
(struct linked_list *)malloc(sizeof (struct linked_list));
first[i] = last[i] = nova;
}
}

and

struct linked_list *
cells_get_cell_ pointer (const int i)
{
struct linked_list *to_return = NULL;
to_return = first[i];
return to_return;
}

there is also a method for putting more elements in a given list,

void
add_element_to_ list (const int i,
const int data)
{
struct linked_list *nova =
(struct linked_list *)malloc(sizeof (struct linked_particle ));
nova->data = data;
struct linked_particle *last_actual = last[i];
if (!last_actual) printf("Error\n ");
linked_particle _add(nova,&last _actual);

return;
}

where

void
linked_particle _add (struct linked_list * to_add,
struct linked_list ** last){
if(!*last) *last = to_add;
else (*last)->next = to_add;
to_add->next = NULL;
*last = to_add;

return;
}

The program seems to work when I add new items to a given list (I get
no errors), but when I try to get the first pointer of a given list in
order to list all the elements, I only get a NULL pointer.
I think I'm missing something, but I don't know what.

Thanks,

[Eric Sosman]

Re: Linked lists and pointers



paudirac wrote:[color=blue]
> Hi,
>
> I need to maintain N linked lists where N is determined at runtime.
> The linked lists are defined as follows,
>
> struct linked_list {
> int data;
> struct linked_list next;
> }
> [...]
> I think I'm missing something, but I don't know what.[/color]

Neither do I, since you haven't shown your source code.
(Yes, you showed *something*, but it obviously isn't your
actual code: the sample above, for example, will not compile.
Now, I know how to fix the two errors in those four lines,
but how many other inaccuracies lurk in the rest of what
you posted? Will I be debugging your code, or merely my
guesses about what your code looks like? If you prefer the
former to the latter, post actual code and not a paraphrase.)

--
Eric.Sosman@sun .com

[CBFalconer]

Re: Linked lists and pointers

paudirac wrote:[color=blue]
>
> I need to maintain N linked lists where N is determined at runtime.
> The linked lists are defined as follows,[/color]

Whenever N is to be determined at runtime, a linked list is very
often the appropriate implementation. Thus you probably want a
linked list of headers to linked lists.

--
"If you want to post a followup via groups.google.c om, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Emmanuel Delahaye]

Re: Linked lists and pointers

paudirac wrote on 16/03/05 :[color=blue]
> I need to maintain N linked lists where N is determined at runtime.
> The linked lists are defined as follows,
>
> struct linked_list {
> int data;
> struct linked_list next;
> }
>
> I think I'm missing something, but I don't know what.[/color]

a '*'

struct linked_list {
int data;
struct linked_list *next;
}

--
Emmanuel
The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html
The C-library: http://www.dinkumware.com/refxc.html

"Mal nommer les choses c'est ajouter du malheur au
monde." -- Albert Camus.

[paudirac]

Re: Linked lists and pointers

Sorry, actually my definitions is the appropiate one,
struct linked_list {
int data;
struct linked_list *next;
}

Excusme for that,

Emmanuel Delahaye wrote:[color=blue]
> paudirac wrote on 16/03/05 :[color=green]
> > I need to maintain N linked lists where N is determined at runtime.
> > The linked lists are defined as follows,
> >
> > struct linked_list {
> > int data;
> > struct linked_list next;
> > }
> >
> > I think I'm missing something, but I don't know what.[/color]
>
> a '*'
>
> struct linked_list {
> int data;
> struct linked_list *next;
> }
>
> --
> Emmanuel
> The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html
> The C-library: http://www.dinkumware.com/refxc.html
>
> "Mal nommer les choses c'est ajouter du malheur au
> monde." -- Albert Camus.[/color]

[Andrey Tarasevich]

Re: Linked lists and pointers

paudirac wrote:[color=blue]
> ...
> I need to maintain N linked lists where N is determined at runtime.
> The linked lists are defined as follows,
>
> struct linked_list {
> int data;
> struct linked_list next;
> }[/color]

struct linked_list* next

This appears to be a type of a _single_ _entry_ of a list.
[color=blue]
> I thought of two arrays of pointers
> struct linked_list **first;
> struct linked_list **last;
> in order to acces the linked_lists.[/color]

OK.
[color=blue]
> I have the following methods,
>
> void
> init_lists(cons t int N)
> {
> first = (struct linked_particle **)calloc(N, sizeof(struct
> linked_particle *));
> last = (struct linked_particle **)malloc(N * sizeof(struct
> linked_particle *));[/color]

What is the importance of using 'calloc' for the first array and
'malloc' for the second? Below you explicitly assign initial values to
the elements of these arrays anyway...

Also, normally you don't have to cast the result of 'malloc' and 'calloc'.
[color=blue]
> int i;
> for (i = 0; i < N; i++) {
> struct linked_particle *nova =
> (struct linked_list *)malloc(sizeof (struct linked_list));
> first[i] = last[i] = nova;
> }
> }[/color]

Hmm... It appears that at initialization stage you are creating a
"dummy" element in each list. I don't exactly see the point in doing
this. But let's accept it for now...
[color=blue]
> and
>
> struct linked_list *
> cells_get_cell_ pointer (const int i)
> {
> struct linked_list *to_return = NULL;
> to_return = first[i];
> return to_return;
> }[/color]

Why don't just do

struct linked_list *
cells_get_cell_ pointer (const int i)
{
return first[i];
}

?
[color=blue]
> there is also a method for putting more elements in a given list,
>
> void
> add_element_to_ list (const int i,
> const int data)
> {
> struct linked_list *nova =
> (struct linked_list *)malloc(sizeof (struct linked_particle ));
> nova->data = data;
> struct linked_particle *last_actual = last[i];
> if (!last_actual) printf("Error\n ");
> linked_particle _add(nova,&last _actual);
>
> return;
> }[/color]

This is obviously wrong. Your 'linked_particl e_add' function modifies
the pointer to the last element of the list through its 'last'
parameter. Here you create and pass a copy ('last_actual') of the
corresponding entry of the 'last' array ('last[i]'). 'last_actual' will
get modified, but 'last[i]' will remain unchanged. This doesn't make
sense and this is why your code doesn't work as expected. Why did you
decide to create a copy here? It is supposed to look more like

void
add_element_to_ list (const int i,
const int data)
{
struct linked_list *nova = malloc(sizeof *nova);
nova->data = data;
linked_particle _add(nova, &last[i]);
}
[color=blue]
> where
>
> void
> linked_particle _add (struct linked_list * to_add,
> struct linked_list ** last){
> if(!*last) *last = to_add;[/color]

What's the point of this check??? Your lists start with one dummy
element already there. '*last' cannot be null here.
[color=blue]
> else (*last)->next = to_add;
> to_add->next = NULL;
> *last = to_add;
>
> return;
> }[/color]

If I were you, I'd get rid of the initial dummy elements in the lists
and also lifted the 'last' pointers to a higher level of indirection.
That would make the code much cleaner

struct linked_list **first;
struct linked_list ***last; /* Note 3 stars */

void init_lists(int N)
{
first = malloc(N * sizeof *first);
last = malloc(N * sizeof *last);

int i;
for (i = 0; i < N; i++) {
first[i] = NULL;
last[i] = &first[i];
/* Note what 'last' array contains now */
}
}

void add_element_to_ list(int i, int data)
{
struct linked_list *nova = malloc(sizeof *nova);
nova->data = data;
linked_particle _add(nova, &last[i]);
}

void linked_particle _add(struct linked_list * to_add,
struct linked_list *** last)
{
to_add->next = NULL;
**last = to_add;
*last = &to_add->next;
/* Note how 'last' is used here */
}

That's it.

--
Best regards,
Andrey Tarasevich

[paudirac]

Re: Linked lists and pointers

Thank you very much, I didn't realized that I was creating a copy
instead of using a pointer. Actually, I'm very new in C and I'm not so
much used to pointers and different levels of indirection yet. Now it
works fine.

Thanks,

Andrey Tarasevich wrote:[color=blue]
> paudirac wrote:[color=green]
> > ...
> > I need to maintain N linked lists where N is determined at runtime.
> > The linked lists are defined as follows,
> >
> > struct linked_list {
> > int data;
> > struct linked_list next;
> > }[/color]
>
> struct linked_list* next
>
> This appears to be a type of a _single_ _entry_ of a list.
>[color=green]
> > I thought of two arrays of pointers
> > struct linked_list **first;
> > struct linked_list **last;
> > in order to acces the linked_lists.[/color]
>
> OK.
>[color=green]
> > I have the following methods,
> >
> > void
> > init_lists(cons t int N)
> > {
> > first = (struct linked_particle **)calloc(N, sizeof(struct
> > linked_particle *));
> > last = (struct linked_particle **)malloc(N * sizeof(struct
> > linked_particle *));[/color]
>
> What is the importance of using 'calloc' for the first array and
> 'malloc' for the second? Below you explicitly assign initial values[/color]
to[color=blue]
> the elements of these arrays anyway...
>
> Also, normally you don't have to cast the result of 'malloc' and[/color]
'calloc'.[color=blue]
>[color=green]
> > int i;
> > for (i = 0; i < N; i++) {
> > struct linked_particle *nova =
> > (struct linked_list *)malloc(sizeof (struct linked_list));
> > first[i] = last[i] = nova;
> > }
> > }[/color]
>
> Hmm... It appears that at initialization stage you are creating a
> "dummy" element in each list. I don't exactly see the point in doing
> this. But let's accept it for now...
>[color=green]
> > and
> >
> > struct linked_list *
> > cells_get_cell_ pointer (const int i)
> > {
> > struct linked_list *to_return = NULL;
> > to_return = first[i];
> > return to_return;
> > }[/color]
>
> Why don't just do
>
> struct linked_list *
> cells_get_cell_ pointer (const int i)
> {
> return first[i];
> }
>
> ?
>[color=green]
> > there is also a method for putting more elements in a given list,
> >
> > void
> > add_element_to_ list (const int i,
> > const int data)
> > {
> > struct linked_list *nova =
> > (struct linked_list *)malloc(sizeof (struct linked_particle ));
> > nova->data = data;
> > struct linked_particle *last_actual = last[i];
> > if (!last_actual) printf("Error\n ");
> > linked_particle _add(nova,&last _actual);
> >
> > return;
> > }[/color]
>
> This is obviously wrong. Your 'linked_particl e_add' function modifies
> the pointer to the last element of the list through its 'last'
> parameter. Here you create and pass a copy ('last_actual') of the
> corresponding entry of the 'last' array ('last[i]'). 'last_actual'[/color]
will[color=blue]
> get modified, but 'last[i]' will remain unchanged. This doesn't make
> sense and this is why your code doesn't work as expected. Why did you
> decide to create a copy here? It is supposed to look more like
>
> void
> add_element_to_ list (const int i,
> const int data)
> {
> struct linked_list *nova = malloc(sizeof *nova);
> nova->data = data;
> linked_particle _add(nova, &last[i]);
> }
>[color=green]
> > where
> >
> > void
> > linked_particle _add (struct linked_list * to_add,
> > struct linked_list ** last){
> > if(!*last) *last = to_add;[/color]
>
> What's the point of this check??? Your lists start with one dummy
> element already there. '*last' cannot be null here.
>[color=green]
> > else (*last)->next = to_add;
> > to_add->next = NULL;
> > *last = to_add;
> >
> > return;
> > }[/color]
>
> If I were you, I'd get rid of the initial dummy elements in the lists
> and also lifted the 'last' pointers to a higher level of indirection.
> That would make the code much cleaner
>
> struct linked_list **first;
> struct linked_list ***last; /* Note 3 stars */
>
> void init_lists(int N)
> {
> first = malloc(N * sizeof *first);
> last = malloc(N * sizeof *last);
>
> int i;
> for (i = 0; i < N; i++) {
> first[i] = NULL;
> last[i] = &first[i];
> /* Note what 'last' array contains now */
> }
> }
>
> void add_element_to_ list(int i, int data)
> {
> struct linked_list *nova = malloc(sizeof *nova);
> nova->data = data;
> linked_particle _add(nova, &last[i]);
> }
>
> void linked_particle _add(struct linked_list * to_add,
> struct linked_list *** last)
> {
> to_add->next = NULL;
> **last = to_add;
> *last = &to_add->next;
> /* Note how 'last' is used here */
> }
>
> That's it.
>
> --
> Best regards,
> Andrey Tarasevich[/color]