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(const 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]

paudirac wrote:

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.

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

--
Er*********@sun.com

[CBFalconer]

paudirac wrote:

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

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.com, 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]

paudirac wrote on 16/03/05 :

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.

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]

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

Excusme for that,

Emmanuel Delahaye wrote:

paudirac wrote on 16/03/05 :

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.

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.

[Andrey Tarasevich]

paudirac wrote:

...
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;
}
struct linked_list* next

This appears to be a type of a _single_ _entry_ of a list.
I thought of two arrays of pointers
struct linked_list **first;
struct linked_list **last;
in order to acces the linked_lists.
OK.
I have the following methods,

void
init_lists(const int N)
{
first = (struct linked_particle **)calloc(N, sizeof(struct
linked_particle *));
last = (struct linked_particle **)malloc(N * sizeof(struct
linked_particle *));
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'.
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;
}
}
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...
and

struct linked_list *
cells_get_cell_pointer (const int i)
{
struct linked_list *to_return = NULL;
to_return = first[i];
return to_return;
}
Why don't just do

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

?
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;
}
This is obviously wrong. Your 'linked_particle_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]);
}
where

void
linked_particle_add (struct linked_list * to_add,
struct linked_list ** last){
if(!*last) *last = to_add;
What's the point of this check??? Your lists start with one dummy
element already there. '*last' cannot be null here.
else (*last)->next = to_add;
to_add->next = NULL;
*last = to_add;

return;
}

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]

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:

paudirac wrote:

...
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;
}
struct linked_list* next

This appears to be a type of a _single_ _entry_ of a list.

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

OK.

I have the following methods,

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

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

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;
}
}
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...

and

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

Why don't just do

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

?

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;
}

This is obviously wrong. Your 'linked_particle_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]);
}

where

void
linked_particle_add (struct linked_list * to_add,
struct linked_list ** last){
if(!*last) *last = to_add;

What's the point of this check??? Your lists start with one dummy
element already there. '*last' cannot be null here.

else (*last)->next = to_add;
to_add->next = NULL;
*last = to_add;

return;
}

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