Linked Lists

In a nutshell

A linked list is a chain of struct Node { int value; struct Node *next; } allocations. The program holds a pointer to the first node (the “head”); each node points to the next; the last node’s next is NULL. Insertion and deletion are O(1) at known positions, O(n) when you have to walk to find the right spot. You trade the cheap arr[i] random access of arrays for the cheap resize/reorder of a chain.

Why it matters

Linked lists are the first data structure where the shape of the data in memory is something you build by hand, one node at a time, with malloc. Every heap bug you learned about in week 5 (leak, use-after-free, double-free) surfaces here. The linked-list mechanics also transfer directly to trees, graphs, hash-table buckets, and nearly every dynamic data structure.

Key takeaways

• Node definition. typedef struct Node { int value; struct Node *next; } Node; — the self-reference needs the struct Node tag because Node alone is not yet defined.
• Head pointer. A Node *head; variable. head == NULL means “empty list.”
• Prepend is O(1). Create a new node, set new_node->next = head;, set head = new_node;.
• Append is O(n). Walk to the last node, set last->next = new_node;.
• Traversal: for (Node *p = head; p != NULL; p = p->next) { ... }.
• Deletion has two pointer arguments: the one you are removing, and the one before it whose next needs to skip the removed node.
• Every malloc needs its free. When you free the list, walk it, save p->next before calling free(p), then move on.

Lessons in this topic

(Lessons for week 8 are being authored; check back or follow the site updates.)

Practice and deep dives

Practice this topic: browse the practice gallery.

What comes next

Recursion on Linked Structures — walking a linked list with a recursive function mirrors the list’s own structure, and sets up the tree traversals to come.