How to typedef a structure including pointers to itself?

Question

Code without typedef (and it works):

struct Node {
    int data;
    struct Node *next;
    struct Node *prev;
};

I'm trying to make a code using typedef for the structure "Node" in Doubly Linked List, but this does not work:

typedef struct {
    int data;
    Node *next;
    Node *prev;
} Node;

Is there a way around this using typedef?

Answer 1

You can use a forward declaration of the struct

typedef struct sNode Node; // this is a typedef and a declaration of the struct
struct sNode{
    int data;
    Node *next;
    Node *prev;
};

This way Node is known (but not defined), in the definition of your struct.

This can be compressed as it is done by Yunnosch. But then you need to use the struct Name notation inside your declaration.

This way it is possible to already use the typedefed name also the forward declaration is necessary if you have some circular dependencies in your structs.

It is also possible to use the struct name as the typedef:

typedef struct Node Node; 
struct Node{
    int data;
    Node *next;
    Node *prev;
};

I personally prefer the first style, it seems "clearer" to me, but there is nothing wrong with the second example, as long as the compiler is not from the pre-standard era (before 1989).

As Jens Gustedt pointed out the first style might be incompatible if this is included in C++.

So maybe I should change my preference to the first.

Answer 2

Inside the typedef, the to-be-defined type is not yet known, so you need to introduce and use a struct tag:

typedef struct Node_tag {
    int data;
    struct Node_tag *next;
    struct Node_tag *prev;
} Node;

The Node_tag is the struct tag, because of where it is introduced (and not because of the name part "_tag"). It is not a type in itself, only the combination as struct Node_tag is a type which can be used for the struct members.
Afterwards, when the typedef is done, the type Node has been defined.
To clarify, a second typedef would be possible as typedef struct Node_tag NodeToo;. This demonstrates that the type struct Node_tag is also useable. That is why I prefer to use the "_tag" name fragment, to allow to be clear of what is used.