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 * — unalignedmemoryaccess
– unalignedmemoryaccess, Commented Jun 8, 2017 at 13:25
Don't hide pointer semantics behind a typedef just to have syntactic sugar. — StoryTeller - Unslander Monica
– StoryTeller - Unslander Monica, Commented Jun 8, 2017 at 13:26
Not a good practice to typedef pointers; this is likely to lead to errors and confusion. — ad absurdum
– ad absurdum, Commented Jun 8, 2017 at 13:27
I know this is not good, but my stupid professor sticks to this way.. lol — nestiank
– nestiank, Commented Jun 8, 2017 at 13:28
"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
– Ingo Leonhardt, Commented Jun 8, 2017 at 13:30

Stephan Lechner · Accepted Answer · 2017-06-08 13:52:38Z

2

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;
}

edited Jun 8, 2017 at 13:52

answered Jun 8, 2017 at 13:45

Stephan Lechner

35.2k4 gold badges38 silver badges59 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Davide Spataro Over a year ago

You are right. It works because next is a pointer and you it is never actually dereferenced. Only the address is passed around and manipulated (which do not really requires node to be complete). If you actually try to print next->val then you will see the problem appearing cause at that point the compiler need to know the size of node which has only been forward declared. Great answer.

gsamaras · Accepted Answer · 2017-06-08 13:39:50Z

0

I do not understand why this works.

It doesn't, you should get compilation errors, like these with gcc 6.3 or 4.2.1:

prog.c: In function ‘makeInitialLinkedList’:
prog.c:15:35: error: ‘node’ undeclared (first use in this function)
         if (rec!=NULL) rec->next=(node*)cur;
                                   ^~~~
prog.c:15:35: note: each undeclared identifier is reported only once for each function it appears in
prog.c:15:40: error: expected expression before ‘)’ token
         if (rec!=NULL) rec->next=(node*)cur;
                                        ^

Live demo by Deduplicator.

is node* a kind of data types like int* or char*?

No. What you have there will result in an error, unless you define node yourself.

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

That's the idea.

edited Jun 8, 2017 at 13:39

answered Jun 8, 2017 at 13:34

gsamaras

73.7k50 gold badges210 silver badges330 bronze badges

3 Comments

nestiank Over a year ago

this runs at dev c++ compiler

Deduplicator Over a year ago

@keist99 See the errors on Coliru: coliru.stacked-crooked.com/a/3512293b47e95856

gsamaras Over a year ago

@keist99 that's an old compiler. Try the code online, in Ideone for example and will get errors! Deduplicator nice, I will inject this link in my answer, if you don't mind. =)

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related