recursive type definitions in C

Question

I'm trying to implement a linked list in C. I have tried the following implementations:

// Attempt 1
typedef struct
{
  Node *next;
  Node *prev;
} Node;

// Attempt 2
typedef struct
{
  struct Node *next;
  struct Node *prev;
} Node;

The first version gives me the error: unknown type name 'Node'

The second compiles but gives warnings: assignment to 'struct Node *' from incompatible pointer type 'Node *' {aka 'struct <anonymous> *'} when I use it like this

void link(Node * node) {
  node->next = (Node) {node, NULL}
}

`(Node) {node, NULL}` should be `(Node*)&{node, NULL}` since `next` is a pointer. — Barmar, Apr 15 '21 at 20:50
Change your `Attempt 2` to `typedef struct Node {...} Node;` — Eugene Sh., Apr 15 '21 at 20:51
However, that would be invalid because the compound literal returns a pointer to local data. — Barmar, Apr 15 '21 at 20:51
What Eugene Sh. says or you can also do `typedef struct Node; struct Node { Node *next,*prev; };` — Petr Skocik, Apr 15 '21 at 20:57

Vlad from Moscow · Accepted Answer · 2021-04-15T21:53:02.570

In this declaration of an unnamed structure within the typedef declaration

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

the name Node used as a type specifier of data members next and prev is undeclared. So the compiler issues an error.

In this declaration of an unnamed structure in the typedef declaration

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

there are introduced the type specifier struct Node and the typedef name Node for the unnamed structure. They are different type specifiers. That is Node and struct Node are not the same specifiers.

What you need is the following

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

Now Node is an alias for the type specifier struct Node.

Pay attention to that this function definition

void link(Node * node) {
  node->next = (Node) {node, NULL}
}

does not make a sense and the compiler shall again issue an error. The left operand of the assignment statement (where you forgot to place a semicolon)

  node->next = (Node) {node, NULL};

has the type Node * or struct Node * (if you will update the typedef declaration as it is shown above) while the right operand is a compound literal of the type struct Node. Moreover the compound literal has automatic storage duration and will not be alive after exiting the function.

So if you will even write

  node->next = &(Node) {node, NULL};

the pointer node->next will be invalid after exiting the function.

You can also declare the type first: `typedef struct Node Node;` and then use the new type in the structure definition: `struct Node { Node *next; Node *prev; };` — user3386109, Apr 15 '21 at 21:03

recursive type definitions in C

1 Answers1