Linked list: Should the type of pointer "next" and the name of struct be same?

Question

#include<stdio.h>
#include<stdlib.h>
typedef struct {
    int val;
    struct node* next;
} Node, *NodePtr;
void makeInitialLinkedList(int a[], int n)
{
    int i;
    NodePtr rec=NULL;
    NodePtr head=NULL;
    for (i=0; i<n; i++) {
        NodePtr cur=(NodePtr)malloc(sizeof(Node));
        if (i==0) head=cur;
        if (rec!=NULL) rec->next=(node*)cur;
        cur->val=a[i];
        cur->next=NULL;
        rec=cur;
    }

    // test
    while(n--) {
        printf("%d ", head->val);
        head=(NodePtr)head->next;
    }
}
NodePtr copy(NodePtr head)
{
    return NULL;
}
int main()
{
    //Mission #2
    int initialDataArray[10]={5,3,2,8,9,7,0,6,4,1};
    makeInitialLinkedList(initialDataArray, 10);

}

I do not understand why this works. I did not make a name initially for the struct and only made a surname "Node" by typedef. Then how does "struct node* next" work correctly? is node* a kind of data types like int* or char*? I thought like this:

typedef struct strName {
    int val;
    struct strName* next;
} strSurName, *strPtr;

Does the type of pointer "next" and the initial name of struct have to same?

In general I believe it is good to have the same type, but it is up to you. It can be also of type void * — tilz0R
Don't hide pointer semantics behind a typedef just to have syntactic sugar. — StoryTeller - Unslander Monica
Not a good practice to typedef pointers; this is likely to lead to errors and confusion. — ad absurdum
I know this is not good, but my stupid professor sticks to this way.. lol — nestiank
"I do not understand why this works." - well the code you've posted does not compile -- because node is not defined just as you thought — Ingo Leonhardt

Stephan Lechner Stephan Lechner · Accepted Answer · 2017-06-08T13:45:38

With struct node* next as a member of your (unnamed) struct, you actually do two things - forward declare a structure struct node and define a member named next as a pointer to the (forward declared) struct node. Note that struct node, as it has been just forward declared, is incomplete and is an additinal, new structure that is different from the enclosing struct you actually wanted to refer to. Confer also struct forward declaration at cppreference:

A declaration of the following form struct name; hides any previously declared meaning for the name name in the tag name space and declares name as a new struct name in current scope, which will be defined later. Until the definition appears, this struct name has incomplete type. This allows structs that refer to each other:

struct y;
struct x { struct y *p; /* ... */ };
struct y { struct x *q; /* ... */ };

So It just seems as if you had a pointer to the same struct you are defining, but actually you are (forward declaring) and using a new structure. See the following example, which actually compiles.

struct known_struct {
    int a[20];
};

struct own_struct {
    int val;
    struct known_struct* known;
    struct own_struct *own;
    struct unknown_struct* unknown;
} test;

int main(){

    size_t sizeOfKnownMember = sizeof(*(test.known));  // gives 80
    size_t sizeOfMemberOwn = sizeof(*(test.own));  // gives 32
    // size_t sizeOfunknownMember = sizeof(*(test.unknown));  // invalid application of sizeof to incomplete type `struct unknown_struct`

    return 0;
}

Linked list: Should the type of pointer "next" and the name of struct be same?

2 Answers