In a C Linked List why are the nodes also pointers? [duplicate]

Question

I could not grasp the reason we create pointers of nodes instead of node structures when we try to implement linked lists as here:

typedef struct node {
    int val;
    struct node * next;
} node_t;

and

node_t * head = NULL;
head = malloc(sizeof(node_t));
if (head == NULL) {
    return 1;
}

head->val = 1;
head->next = NULL;

here, why do we declare nodes such as head as pointers of structures instead of direct structures>

Answer 1

Having head as a pointer allows for things like empty lists (head == NULL) or a simple way to delete elements at the front of the list, by moving the head pointer to another (e.g. second) element in the list. Having head as a structure, these operations would be impossible or at least much less efficient to implement.

Answer 2

The primary reason is that the C language simply won't allow it - a struct type cannot contain an instance of itself. There are two reasons for this:

1. The struct type is not complete until the closing }, and you cannot create an instance of an incomplete type;

2. If a struct type could contain an instance of itself, then the instance would be infinitely large (struct foo contains an instance of struct foo, which contains an instance of struct foo, which contains an instance of struct foo, ad infinitum).

You can, however, create pointers to incomplete types (since the size of the pointer doesn't depend on the size of the pointed-to type). So if you want a struct type to contain a member that refers to another instance of the same type, it must be done through a pointer.