A linked list node is a struct with a data field and a pointer to the next node of the same type — this self-reference is valid because a pointer needs to know neither a type's size nor its full definition at the point it's declared, only that the type's name exists. Every pointer is the same fixed size regardless of what it points to (a pointer to a 1000-byte struct and a pointer to an int are the same number of bytes) — which is exactly why struct Node *next; compiles inside struct Node's own definition, before the struct's size is even known. Each node is individually allocated with malloc and connected by storing one node's address in the previous node's next pointer; C provides no built-in linked list type, so the entire structure, traversal, insertion, and cleanup logic is written by hand.
The self-referential struct
struct Node *next works because the struct only needs a POINTER to another Node, and a pointer's size is fixed and known regardless of what it points to — struct Node next (without the *) would be illegal, since that would require infinite memory to hold a Node containing a Node containing a Node forever.
typedef struct Node {
int data;
struct Node *next; // a POINTER to another Node — this is what makes it valid
} Node;Building the list: inserting at the head
Inserting at the head is O(1) — the new node's next simply points to whatever the old head was, then head is updated to point at the new node.
Node *insertHead(Node *head, int value) {
Node *newNode = malloc(sizeof(Node));
newNode->data = value;
newNode->next = head; // new node points to the OLD head
return newNode; // the new node IS the new head
}
Node *list = NULL;
list = insertHead(list, 3);
list = insertHead(list, 2);
list = insertHead(list, 1); // list is now: 1 -> 2 -> 3 -> NULLTraversing and freeing every node
Freeing a node BEFORE saving its next pointer would lose the rest of the list entirely — the temp variable exists specifically to avoid this exact ordering mistake, a genuinely easy one to make.
void printList(Node *head) {
Node *current = head;
while (current != NULL) {
printf("%d -> ", current->data);
current = current->next;
}
printf("NULL\n");
}
void freeList(Node *head) {
Node *current = head;
while (current != NULL) {
Node *next = current->next; // save BEFORE freeing — order matters
free(current);
current = next;
}
}