c++cstructlinked-list

How does C/CPP know how to point to "next" struct node when the struct node is not yet defined?


When creating singly linked lists, it is common to create a Node struct as follows:

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

However, I was wondering how does the pointer to the next node next knows what struct node is if node's definition has not been done yet.

I have read from quora that the compiler fails to compile the following:

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

giving the following error:

a.c:6:13: error: field has incomplete type 'struct node' 
struct node next; 
            ^ 
a.c:4:8: note: definition of 'struct node' is not complete until the closing '}' 
struct node { 
       ^ 
1 error generated. 

If the definition of node struct is not done before '}' is used, then how come can we set the pointer to an undefined user-defined data type node?


Solution

  • Because next is a pointer to node, the type does not need to be complete in order for compilation to succeed.

    Consider also a simple example in C++. The type of A does not need to be complete in order to have a pointer to it in struct B. Be prepared to see this pattern used to resolve circular dependencies.

    struct A;
    
    struct B {
        A *c;
    };
    
    struct A {
        B *d;
    };
    

    Please note that C and C++ are two distinct programming languages, and while specific chunks of C code may be valid C++, it is not guaranteed that it will be, or even that if it is, that it will behave with exactly the same semantics.