Understanding typedef with struct

Question

I am getting a hard time understanding this sample of code:

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

typedef node * nodepointer;

So, we are building the struct node using typedef... I assume we are doing this in order to initialize the struct without the "struct" keyword being necessary.

I want to ask why in the struct definition we used the name "node" twice (at start and end).

Secondly what typedef node * nodepointer; points to. Is it necessary to use typedef in this case? Is this expression node * nodepointer; not equal?

Answer 1

First off, let's be clear here: a typedef isn't a declaration of a variable. It simply aliases a new type name to an existing type specifier.

typedef <type specifier> new_type_name;

---

So what's going on here can certainly be deceiving to the untrained eye.

struct node itself is a struct called node with the two properties int data and a struct node *next.

I'll go more into next in a moment, but for now this is simple enough.

Then, the surrounding typedef takes that struct and gives it the name node. Why is this, you might ask?

This is due to the fact that in C (unlike C++) using structs by their tag name requires prefixing the type with struct.

struct Foo {
    // ...
};

Foo bar; // ERROR
struct Foo bar; // OK

Using a typedef, we alias the struct with a typename, called node. This example should make it a bit more clear.

typedef struct Foo {
    // ...
} FooType;

Foo bar; // ERROR
struct Foo bar; // OK

FooType bar; // OK
struct FooType bar; // ERROR

Keep in mind you can define structs without tags, and thus typedef them.

typedef struct {
    // ...
} FooType;

FooType bar; // OK

Though I'll explain why you can't do this in your example.

The property struct node *next in your example is an incomplete type. Incomplete types, simply put, are types that have been declared (given a name and a type, i.e. struct node;), but not defined (given a 'body', i.e. struct node { int foo; };).

Incomplete types cannot be used until they are defined, unless you're pointing to them.

struct Foo;

struct Foo bar; // ERROR: Foo is not defined.
struct Foo *bar; // OK - it's just a pointer. We know the size of a pointer.

struct Foo {
    // ...
};

struct Foo bar; // OK - it's defined now.

So by the type struct node *next is declared, we already have the declaration of struct node but not the definition, which makes a pointer to struct node possible.

You can also infer, too, that using struct node directly would not work:

struct node {
    struct node next; // ERROR - `struct node` becomes infinitely big
    struct node *next; // OK - a pointer is usually 4/8 bytes (we at least know its size at this point)
};

---

To answer your last three questions:

What [does] typedef node * nodepointer; [point] to[?]

Nothing. It's just an alias (a label, or a 'nickname') to another type. It simply says that the type nodepointer is really a node *.

This also means anything that requires a node * can thus use a nodepointer, and vice versa.

Is it necessary to use typedef in this case?

Not necessary, no. You could just as well use node * everywhere instead of nodepointer. Most coding standards frown upon typedefing types to their pointer types (like your example) because it adds confusion to the code base (as you have demonstrated by this very question! :))

Is [the] expression node * nodepointer; not equal?

Nope. Again, remember typedef simply specifies another way to reference the same type. It doesn't actually create any memory, rather gives a new name to an existing type.

Answer 2

This struct is self referential which means it contains a pointer to itself.

if you don't use tag node, How will you specify pointer type later. Hence first node is required

struct node {
    struct node *ptr;    
};
// you can do this way too
typdef struct node node;

The last node is required for completing the typedef.

By typedef node * nodepointer;, Now you can use nodepointer to mean node*. Wherever node* occurs, you can simply replace with nodepointer

Is it necessary to use typedef in this case?

It is upto you,

Is this expression node * nodepointer; not equal?

No, this only declares nodepointer to be pointer variable whereas typedef creates alias of type, node * by the name nodepointer.

Answer 3

typedef struct node
    int data;
    struct node * next;
} node;

The node in the first line is the tag of the structure.

The node in the last line is the name of the type.

These two do not have to be identical.

If you want them to be different the code will be as follows.

typedef struct helloNode
    int data;
    struct helloNode * next;
} node;    

The name of the type is node. The name of the structure is helloNode

For a more technical explanation, these two nodes are in different namespaces. and can have different values.

From section 6.3 of http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf

If more than one declaration of a particular identifier is visible at any point in a translation unit, the syntactic context disambiguates uses that refer to different entities. Thus, there are separate name spaces for various categories of identifiers, as follows:

— label names (disambiguated by the syntax of the label declaration and use);

— the tags of structures, unions, and enumerations (disambiguated by following any32) of the keywords struct, union, or enum);

— the members of structures or unions; each structure or union has a separate name space for its members (disambiguated by the type of the expression used to access the member via the . or -> operator);

— all other identifiers, called ordinary identifiers (declared in ordinary declarators or as enumeration constants).

Answer 4

The question is that you are doing two things at once: declaring struct type and typedefing that struct to a name.

For typedef the syntax is

typedef <some type> name;

where some type may be a simple type, like int, long, etc. or a complex one like struct foo, and this regardless of wether struct foo has been declared before or it's being declared at that very point.

So

typedef struct foo { int bar; } foo;

Corresponds to

typedef <some type> name;

where <some type> is struct foo { int bar; } and name is foo

As to the second question,

In this case <some type> is node * and name is nodepointer, so

typedef node * nodepointer;

is typedefing a nodepointer as a pointer to a node (which you have typedefd just before to be a struct node { ... })

Answer 5

Daleisha said correctly that you need the struct tag in order to declare the pointer next which points to just these structures. You cannot write that type name down before it is introduced. Another possibility is to forward-declare the struct:

struct node;
typedef struct node node;

struct node
{
    node *next;
    int i;
};

But that introduces rather more mentionings of one node or another.

As a side effect, introducing the struct tag "node" makes it possible to still write the normal struct node, which the typedef alone would not make possible.

The second typedef is also still a typedef, it doesn't introduce a variable but a type name. After all the declarations in your source snippet you can say

struct node *np1;
node *np1;
nodepointer np1;

These are all equivalent.

The co-existence of the two type names node and struct node is possible because "struct tags" (like the "node" in "struct node"), as they are called, are held separately from other names and can therefore be used to name something else, additionally, without collision. To typedef a struct so that the new type has the name of the struct tag is a common example, but the name "node" could be used for anything else instead (an int variable, whatever).

Answer 6

For the struct, you are defining your structure name (before the braces) and then the type name (after the braces):

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

The next one creates another type, a pointer to nodes:

 typedef node* nodepointer;

Both can now be used to create variables:

 node myNode;
 nodepointer aPtr;