Linked lists in C
Build a singly linked list in C with malloc, push to the front, walk it, reverse it, and free it.
A linked list is a chain of nodes on the heap, each holding a value and a pointer to the next node. The last node's next is NULL.
Pushing to the front is O(1): make a node, point it at the old head, and it becomes the new head. Walking the list follows next until NULL. To free the list, save next before freeing each node.
Linked lists teach pointers well, but for most real programs a dynamic array (like std::vector) is faster because its elements sit together in memory.
Example
#include <stdio.h>
#include <stdlib.h>
struct node {
int value;
struct node *next;
};
int main(void) {
struct node *head = NULL;
for (int v = 1; v <= 3; v++) {
struct node *n = malloc(sizeof *n);
if (!n) return 1;
n->value = v;
n->next = head;
head = n;
}
for (struct node *p = head; p; p = p->next) printf("%d ", p->value);
printf("\n");
while (head) {
struct node *next = head->next;
free(head);
head = next;
}
return 0;
}
Output:
3 2 1
Watch it run: Building a linked list