Step 2 of 6
Push to the front
Real lists create nodes on the heap, one malloc per node, so the list can grow as long as needed. The easiest insertion is at the front:
- Allocate a new node and fill in its value.
- Point its
nextat the current head. - Make the new node the head.
The order matters: if you replaced the head first, you'd lose the pointer to the rest of the list.
Changing the caller's head
Step 3 changes the head pointer, which belongs to the caller. As you saw with pointers to pointers, a function that must change the caller's pointer needs the address of that pointer, so the parameter is struct Node **head. Inside, *head is the caller's head pointer.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int value;
struct Node *next;
};
int push_back(struct Node **head, int value) {
struct Node *n = malloc(sizeof *n);
if (n == NULL) return 0;
n->value = value;
n->next = NULL;
struct Node **link = head;
while (*link != NULL) {
link = &(*link)->next;
}
*link = n;
return 1;
}
int main(void) {
struct Node *list = NULL;
push_back(&list, 1);
push_back(&list, 2);
push_back(&list, 3);
for (struct Node *p = list; p; p = p->next) printf("%d ", p->value);
printf("\n");
while (list) {
struct Node *next = list->next;
free(list);
list = next;
}
return 0;
}
1 2 3
This example adds at the back instead: it walks a pointer-to-a-link until it finds the NULL at the end and attaches the node there. Adding at the back takes a walk through the whole list (O(n)); adding at the front is immediate (O(1)), which is why push-front is the basic list operation.
Your turn: implement it.