In the C Linked List, why are nodes also pointers?

Question

I could not understand the reason why we create node pointers instead of node structures when we try to implement linked lists, like 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 to structures instead of direct structures>

Answer 1

Having head as a pointer allows things like empty lists ( head == NULL ) or an easy way to remove items at the beginning of a list by moving the head pointer to another (for example, second) item in the list. Having a head as a structure, these operations will be impossible or at least much less efficient to implement.

Answer 2

The main reason is that C simply will not allow this - the struct type cannot contain an instance of itself. There are two reasons for this:

• The struct type is not completed before closing } , and you cannot create an instance of an incomplete type;

• If the struct type can contain an instance of itself, then the instance will 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 , to infinity).

However, you can create pointers to incomplete types (since the size of the pointer does not depend on the size of the specified type). Therefore, if you want the struct type to contain an element that refers to another instance of the same type, it must be executed using a pointer.

Answer 3

why do we declare nodes like head, like pointers to structures instead of direct structures.

Declaring head as a pointer allows us to have an empty list, i.e. when head is NULL

Answer 4

Because the whole point: a set of nodes that are connected as a chain. You can easily and easily disconnect and reconnect nodes, because for this you only need to change the pointer values. This would not be possible if your type looked more like an array. If you want this, use an array.

In addition, it is not possible for the type to contain the instance itself. So a node contains a node that contains a node that contains a node that contains a node , etc. & Hellip; how can it work?

Answer 5

As someone else said, using pointers we have a convenient way to specify an empty list or the end of a list using a NULL pointer.

We could, of course, modify our nodes to have a flag indicating that this is the "end of the list" (EOL). However, another important reason this gives the list the ability to easily grow (up to the amount of available memory) or shrink dynamically without reallocating memory to hold the entire list and copy it every time it grows or shrinks. It also makes it easier to insert or delete an item.

Answer 6

This will not be a “linked” list unless the nodes are actually connected to each other. It can still be a list of some type, but it will not be linked.

Compare to the word link or hyperlink on the Internet. They are also pointers, because there are practically no sites that store actual data from related sites.