Linked Lists in C
A linked list is a chain of nodes, each holding some data plus a pointer to the next node. It's about as simple as a dynamic data structure gets, and the conceptual stepping stone to almost every fancier one.
Node Structure
typedef struct Node { int data; struct Node *next;} Node;Note the struct Node inside the body. The typedef name Node doesn't exist yet at the point of the self-reference, so the explicit tag is required.
Creating Nodes
Node* create_node(int value) { Node *n = malloc(sizeof(Node)); if (n == NULL) return NULL; n->data = value; n->next = NULL; return n;}Building a List
Node *head = NULL;
// Push to front (O(1))Node *new_node = create_node(42);new_node->next = head;head = new_node;Say the list already holds 7 and 3. The two assignments rewire it like this:
The order matters. Run head = new_node first and the only pointer to 7 is gone before you've copied it: the new node points at itself, and the old list leaks.
Traversing a List
void print_list(Node *head) { Node *current = head; while (current != NULL) { printf("%d -> ", current->data); current = current->next; } printf("NULL\n");}Deleting by Value
Deleting is where linked-list code usually gets ugly, because the head is a special case: there's no previous node whose next you can patch. The usual workaround tracks a prev pointer and adds an if for the head. A neater trick walks a pointer to the link itself (Node **pp), so the head pointer and every next field look the same.
Notice that delete_value takes Node **head. It may need to change the caller's head pointer, and by now you know what that means in a pass-by-value language.
Every node is a separate heap allocation, and the only thing holding the structure together is the pointer in each node's next. Lose the head before you free? That's a leak — the nodes are still allocated and unreachable. Free a node while another pointer aims at it? Dangling pointer, congratulations, you've earned a bug that may or may not crash today.
Freeing a List
There's no bulk-delete; you walk the chain and free each node yourself:
void free_list(Node *head) { Node *current = head; while (current != NULL) { Node *next = current->next; free(current); current = next; }}The trick: stash current->next before the free. The instant you call free(current), dereferencing it is undefined — you've already let go of the link to the rest of the list.
When to Use Linked Lists
Linked lists shine when you're constantly inserting and deleting in the middle. Random access is awful — you walk from the head every time. In real benchmarks, arrays and realloc-grown dynamic vectors often beat them outright thanks to cache locality. Still, every pointer-based data structure you'll ever build leans on the same intuitions you sharpen here.