Recursive structure?

[dspfun]

I've come a across a program that declares the following data
structure.

typedef struct node {
struct node *next;
} node;

It looks like a recursive data structure but I'm having trouble
understanding the use of it? Can somebody explain this?

How much memory will be allocated by the compiler when the structure is
instantiated?

The following structure makes use of the previous structure.

typedef struct queue {
node *head, *tail;
} queue;

Best regards!

 

[Lew Pitcher]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

I've come a across a program that declares the following data
structure.

typedef struct node {
struct node *next;
} node;

It looks like a recursive data structure

Not really, but you /are/ close. First off, the quoted text isn't a
structure, it is a typedef. A typedef defines a name that will be
associated to a simple or complex storage type. In this case, the type
associated to the name "node' just happens to be a structure definition
called "node".

but I'm having trouble
understanding the use of it? Can somebody explain this?

Sure.

Assuming that you are concerned about the

struct node {
struct node *next;
};

portion of the typedef, then the structure definition called "node"
contains a /pointer/ (of the type "pointer to struct node").

How much memory will be allocated by the compiler when the structure is
instantiated?

First off, "instantiation" isn't the term to use. But, I know what you
mean.

How much memory?? Well, it will be
sizeof(struct node)
bytes long.

What's the "real" value, you ask? We can't tell you, other than to say
that it will be at least big enough to hold a pointer to a structure.
The structure /may/ be allocated with invisible padding/alignment
bytes, making the structure bigger than the sum of it's components, but
that's up to the compiler to determine. Also, depending on your
compiler, a pointer to struct node may be larger, smaller, or the same
size as any other pointer. Again, this is implementation dependant.

[snip]


HTH

- --
Lew Pitcher

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (MingW32) - WinPT 0.11.12

iD8DBQFE2fYCagVFX4UWr64RAsvqAKDoqBMdCETJhrKiFqbcTj1h7mwKBwCg4MMf
esqUVrmtlZg6juKjuZpIHV8=
=ERDL
-----END PGP SIGNATURE-----

 

[dspfun]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1



Not really, but you /are/ close. First off, the quoted text isn't a
structure, it is a typedef. A typedef defines a name that will be
associated to a simple or complex storage type. In this case, the type
associated to the name "node' just happens to be a structure definition
called "node".


Sure.

Assuming that you are concerned about the
portion of the typedef, then the structure definition called "node"
contains a /pointer/ (of the type "pointer to struct node").

Yes, this is exactly what I don't understand, how can "structure node"
contain a pointer of the type "pointer to struct node"? It seems that
"struct node" is not declared readily? How can the compiler know what
to do? To me it seems analogous to saying "x has the value x".

How much memory will be allocated by the compiler when the structure is
instantiated?

First off, "instantiation" isn't the term to use. But, I know what you
mean.

How much memory?? Well, it will be
sizeof(struct node)
bytes long.

What's the "real" value, you ask? We can't tell you, other than to say
that it will be at least big enough to hold a pointer to a structure.
The structure /may/ be allocated with invisible padding/alignment
bytes, making the structure bigger than the sum of it's components, but
that's up to the compiler to determine. Also, depending on your
compiler, a pointer to struct node may be larger, smaller, or the same
size as any other pointer. Again, this is implementation dependant.

[snip]


HTH

- --
Lew Pitcher

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.3 (MingW32) - WinPT 0.11.12

iD8DBQFE2fYCagVFX4UWr64RAsvqAKDoqBMdCETJhrKiFqbcTj1h7mwKBwCg4MMf
esqUVrmtlZg6juKjuZpIHV8=
=ERDL
-----END PGP SIGNATURE-----

 

[Ancient_Hacker]

Yes, this is exactly what I don't understand, how can "structure node"
contain a pointer of the type "pointer to struct node"? It seems that
"struct node" is not declared readily? How can the compiler know what
to do? To me it seems analogous to saying "x has the value x".

Ah, quite perceptive of you. But it does work because:

(1) What's included is a POINTER to a variable of the same type.

(2) On most every system I can think of, except perhaps some weird ol
Burroughs, a POINTER is just an address. And the address of anything,
no matter what the size, shape or type of the thing, the address is
just a fixed number of bits, often 16, 32, 48, or 64 bits.

(3) So when the compiler sees: struct foo{ foo * nextfoo; it goes
"okay, foo hasnt been fully declared yet, in fact, I may not even be
aware that there is a foo being declared, but a pointer to anything is
just 32 bits, I know how to allocate that"

(4) Eventually foo will come to an end and everything will be okay.

----

It can get even a bit more abstract, you can define ahead of time:

typedef foo * PtrToFoo;

and that will be accepted, as the compiler "knows" you may be intending
to do the same thing as above. of course eventually the base type has
to be defined somewheere.

 

[Giorgio Silvestri]

Yes, this is exactly what I don't understand, how can "structure node"
contain a pointer of the type "pointer to struct node"? It seems that
"struct node" is not declared readily? How can the compiler know what
to do? To me it seems analogous to saying "x has the value x".

No. It is different.
If you say "struct x" I don't know the size, but
if you say (struct x *) I know the size, representation
and alignment, for each 'x'.

 

[Chris Dollin]

dspfun wrote:

Yes, this is exactly what I don't understand, how can "structure node"
contain a pointer of the type "pointer to struct node"?

Why could it not?

It seems that
"struct node" is not declared readily?

Doesn't matter: the compiler knows how to do a /pointer/ to /any/ struct.

If it said `struct node { struct node infinite; };` then there would
be a problem.

 

[dspfun]

dspfun wrote:



Why could it not?


Doesn't matter: the compiler knows how to do a /pointer/ to /any/ struct.

If it said `struct node { struct node infinite; };` then there would
be a problem.

I understand now that the compiler knows how to do a pointer to /any/
struct.

But, if I declare:
node *mynode;

Then I have declared a pointer to a node struct. But all node struct
contains is a pointer to a node struct. I can't see anything useful
with this, however, since it is used it must be good for something.

Can someone give some example of what this (mynode pointer) is good
for?

Wouldn't it be equally good to declare node struct like this?:

struct node {
void *next;
};

 

[Morris Dovey]

dspfun (in (e-mail address removed)) said:

| Chris Dollin wrote:
|| dspfun wrote:
||
||
||| Lew Pitcher wrote:
|||| Assuming that you are concerned about the
||||| struct node {
||||| struct node *next;
||||| };
|||| portion of the typedef, then the structure definition called
|||| "node" contains a /pointer/ (of the type "pointer to struct
|||| node").
||||
|||
||| Yes, this is exactly what I don't understand, how can "structure
||| node" contain a pointer of the type "pointer to struct node"?
||
|| Why could it not?
||
||| It seems that
||| "struct node" is not declared readily?
||
|| Doesn't matter: the compiler knows how to do a /pointer/ to /any/
|| struct.
||
|| If it said `struct node { struct node infinite; };` then there
|| would
|| be a problem.
|
| I understand now that the compiler knows how to do a pointer to
| /any/ struct.
|
| But, if I declare:
| node *mynode;
|
| Then I have declared a pointer to a node struct. But all node struct
| contains is a pointer to a node struct. I can't see anything useful
| with this, however, since it is used it must be good for something.
|
| Can someone give some example of what this (mynode pointer) is good
| for?

It's not unusual to see something like:

node *head; /* Pointer to first element */
node *tail; /* Pointer to final element */

or even:

struct
{ node *head;
node *tail;
} mylist;

to provide a "root" for a list.

| Wouldn't it be equally good to declare node struct like this?:
|
| struct node {
| void *next;
| };

Certainly.

 

[Morris Dovey]

Morris Dovey (in [email protected]) said:

| dspfun (in (e-mail address removed))
| said:
|
|| struct node {
|| void *next;
|| };
|
| Certainly.

Oops! I missed the 'void'. It would _not_ be better.

 

[dspfun]

dspfun (in (e-mail address removed)) said:

| Chris Dollin wrote:
|| dspfun wrote:
||
||
||| Lew Pitcher wrote:
|||| Assuming that you are concerned about the
||||| struct node {
||||| struct node *next;
||||| };
|||| portion of the typedef, then the structure definition called
|||| "node" contains a /pointer/ (of the type "pointer to struct
|||| node").
||||
|||
||| Yes, this is exactly what I don't understand, how can "structure
||| node" contain a pointer of the type "pointer to struct node"?
||
|| Why could it not?
||
||| It seems that
||| "struct node" is not declared readily?
||
|| Doesn't matter: the compiler knows how to do a /pointer/ to /any/
|| struct.
||
|| If it said `struct node { struct node infinite; };` then there
|| would
|| be a problem.
|
| I understand now that the compiler knows how to do a pointer to
| /any/ struct.
|
| But, if I declare:
| node *mynode;
|
| Then I have declared a pointer to a node struct. But all node struct
| contains is a pointer to a node struct. I can't see anything useful
| with this, however, since it is used it must be good for something.
|
| Can someone give some example of what this (mynode pointer) is good
| for?

It's not unusual to see something like:

node *head; /* Pointer to first element */
node *tail; /* Pointer to final element */

or even:

struct
{ node *head;
node *tail;
} mylist;

to provide a "root" for a list.

I'm probably missing something here because I don't see what the
purpose of such a list would be, all it is is a list of node pointers,
isn't it? What is the use of such a list? Wouldn't one like to have
some data at each entry of a list?

 

[Ancient_Hacker]

dspfun wrote:

I'm probably missing something here because I don't see what the
purpose of such a list would be, all it is is a list of node pointers,
isn't it? What is the use of such a list? Wouldn't one like to have
some data at each entry of a list?

Which is easier to carry around:


(1) The key to your house.

(2) Your house.

 

[Keith Thompson]

Morris Dovey wrote: [...]

It's not unusual to see something like:

node *head; /* Pointer to first element */
node *tail; /* Pointer to final element */

or even:

struct
{ node *head;
node *tail;
} mylist;

to provide a "root" for a list.

I'm probably missing something here because I don't see what the
purpose of such a list would be, all it is is a list of node pointers,
isn't it? What is the use of such a list? Wouldn't one like to have
some data at each entry of a list?

Yes, absolutely. A linked list with no actual data isn't much use,
except as a demonstration.

Possibly Morris thought that adding an extra "payload" member would
distract from the main point.

 

[Morris Dovey]

Keith Thompson (in (e-mail address removed)) said:

|| Morris Dovey wrote:
| [...]
||| It's not unusual to see something like:
|||
||| node *head; /* Pointer to first element */
||| node *tail; /* Pointer to final element */
|||
||| or even:
|||
||| struct
||| { node *head;
||| node *tail;
||| } mylist;
|||
||| to provide a "root" for a list.
||
|| I'm probably missing something here because I don't see what the
|| purpose of such a list would be, all it is is a list of node
|| pointers, isn't it? What is the use of such a list? Wouldn't one
|| like to have some data at each entry of a list?
|
| Yes, absolutely. A linked list with no actual data isn't much use,
| except as a demonstration.
|
| Possibly Morris thought that adding an extra "payload" member would
| distract from the main point.

You can get a glimpse of my tortured thought processes in
http://www.iedu.com/mrd/c/queue.c

I'm inclined to define elements (nodes) like:

typedef struct element_d
{ struct element_d *link;
/* Payload data */
} element;

and then declare a list control structure (without payload):

struct
{ element *head;
element *tail;
} some_list = { NULL,NULL };

because it's not unusual for me to have several lists being
manipulated within the same application. It's generally more
economical to pass a pointer to some_list in one situation; or to pass
a pointer to some_other_list elsewhere so that a set of common list
manipulation functions can massage either list.

 

[dspfun]

Keith Thompson (in (e-mail address removed)) said:

|| Morris Dovey wrote:
| [...]
||| It's not unusual to see something like:
|||
||| node *head; /* Pointer to first element */
||| node *tail; /* Pointer to final element */
|||
||| or even:
|||
||| struct
||| { node *head;
||| node *tail;
||| } mylist;
|||
||| to provide a "root" for a list.
||
|| I'm probably missing something here because I don't see what the
|| purpose of such a list would be, all it is is a list of node
|| pointers, isn't it? What is the use of such a list? Wouldn't one
|| like to have some data at each entry of a list?
|
| Yes, absolutely. A linked list with no actual data isn't much use,
| except as a demonstration.
|
| Possibly Morris thought that adding an extra "payload" member would
| distract from the main point.

You can get a glimpse of my tortured thought processes in
http://www.iedu.com/mrd/c/queue.c

I'm inclined to define elements (nodes) like:

typedef struct element_d
{ struct element_d *link;
/* Payload data */
} element;

and then declare a list control structure (without payload):

struct
{ element *head;
element *tail;
} some_list = { NULL,NULL };

because it's not unusual for me to have several lists being
manipulated within the same application. It's generally more
economical to pass a pointer to some_list in one situation; or to pass
a pointer to some_other_list elsewhere so that a set of common list
manipulation functions can massage either list.

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto

Ok, I'm starting to understand it now!

Thank you all for your help, you've been very kind!

The code I was reading is from:

http://www.gentoo.org/doc/en/articles/l-posix3.xml

BR!

 

[dspfun]

Morris Dovey (in [email protected]) said:

| dspfun (in (e-mail address removed))
| said:
|
|| struct node {
|| void *next;
|| };
|
| Certainly.

Oops! I missed the 'void'. It would _not_ be better.

--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto

Is the reason of the void pointer solution not being better that you
can't access the members of the void pointer without doing a cast first
to some specific type?

 

[Morris Dovey]

dspfun (in (e-mail address removed))
said:

| Morris Dovey wrote:
|| Morris Dovey (in [email protected]) said:
||
||| dspfun (in (e-mail address removed))
||| said:
|||
|||| struct node {
|||| void *next;
|||| };
|||
||| Certainly.
||
|| Oops! I missed the 'void'. It would _not_ be better.
|
| Is the reason of the void pointer solution not being better that you
| can't access the members of the void pointer without doing a cast
| first to some specific type?

You're on the right track. I think "better" is providing the compiler
with the information needed to eliminate (or at least minimize) casts.

The biggest benefit, for me, is that this approach allows the compiler
to complain when I do something stupid.

 

[Keith Thompson]

Morris Dovey (in [email protected]) said: [...]
--
Morris Dovey
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto

Is the reason of the void pointer solution not being better that you
can't access the members of the void pointer without doing a cast first
to some specific type?

Please don't quote signatures unless you're actually commenting on
them. We appreciate the fact that you're providing context in your
followups, but quoting signatures, or anything else that isn't
relevant to your followup, is just clutter.

 

[dspfun]

Would you say that this is the best (most processor cycle effective,
least memory consuming and least bug prone) way to implement a linked
list in C?

 

[Morris Dovey]

dspfun (in (e-mail address removed))
said:

| Would you say that this is the best (most processor cycle effective,
| least memory consuming and least bug prone) way to implement a
| linked list in C?

Hmm. I have no *this pointer.

Nope. The best way to implement a linked list depends on the problem
you're solving. Lists can be singly- or multiply-linked, they may
optimized for FIFO or LIFO (or other) access, and they may be
unordered or ordered in about any way imaginable.

_You_ get to decide what works best.

[ Reminds me of a movie in which the last words said of one of the
characters was "He chose unwisely." ]

 

[Keith Thompson]

Would you say that this is the best (most processor cycle effective,
least memory consuming and least bug prone) way to implement a linked
list in C?

What is? Please provide enough context so we can understand what
you're talking about without seeing the parent article.