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 only needs to know a type's SIZE, not its full definition, at the point it's declared. 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;
}
}