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
dspfun wrote:

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, "instantiat ion" 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

iD8DBQFE2fYCagV FX4UWr64RAsvqAK DoqBMdCETJhrKiF qbcTj1h7mwKBwCg 4MMf
esqUVrmtlZg6juK juZpIHV8=
=ERDL
-----END PGP SIGNATURE-----

[dspfun]

Lew Pitcher wrote:

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

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

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, "instantiat ion" 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

iD8DBQFE2fYCagV FX4UWr64RAsvqAK DoqBMdCETJhrKiF qbcTj1h7mwKBwCg 4MMf
esqUVrmtlZg6juK juZpIHV8=
=ERDL
-----END PGP SIGNATURE-----

[Ancient_Hacker]

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"? 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]

"dspfun" <ds****@hotmail .comha scritto nel messaggio
news:11******** **************@ i3g2000cwc.goog legroups.com...

>
Lew Pitcher wrote:

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

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

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

--
Giorgio Silvestri
DSP/Embedded/Real Time OS Software Engineer

[Chris Dollin]

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.

--
Chris "seeker" Dollin
A rock is not a fact. A rock is a rock.

[dspfun]

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.

--
Chris "seeker" Dollin
A rock is not a fact. A rock is a rock.

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 11************* *********@75g20 00...legro ups.com) 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
DeSoto Solar
DeSoto, Iowa USA
http://www.iedu.com/DeSoto

[Morris Dovey]

Morris Dovey (in 44************* **********@news .qwest.net) said:

| dspfun (in 11************* *********@75g20 00...legro ups.com)
| 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

[dspfun]

Morris Dovey wrote:

dspfun (in 11************* *********@75g20 00...legro ups.com) 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?

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

Certainly.

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