Skip to main content
Be Bitwise
CStructs & Data Structures

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

c
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

c
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

c
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

c
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.

Try itRun it, then try deleting a value that isn't in the list, and the only remaining node.
C (GCC 9.2.0)

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.

Key Concept

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:

c
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.