Building Data Structures From Scratch

Course 3 · Ch 2

What Rust's Vec and HashMap do for you, none of which exists in plain C

C's standard library has no growable list, no hash map, nothing beyond fixed-size arrays. This chapter builds two of the most fundamental structures by hand — deliberately, to see exactly what a language's standard collections are actually doing underneath.

No Standard Containers

Rust's Vec and HashMap are genuinely part of the language's own standard toolkit — reach for them, they're just there. C offers nothing equivalent at all. Every real C project either hand-rolls its own structures, exactly as this chapter does, or pulls in a third-party library. This is a real, structural gap, not a minor inconvenience.

A Singly Linked List

typedef struct Node {
    int value;
    struct Node *next;
} Node;

Node *push_front(Node *head, int value) {
    Node *n = malloc(sizeof(Node));
    n->value = value;
    n->next = head;
    return n; // the new head
}

Every node is its own heap allocation — exactly c2-2's discipline, now applied repeatedly, once per node.

Traversing and Freeing the List

void free_list(Node *head) {
    while (head != NULL) {
        Node *next = head->next; // save next BEFORE freeing head
        free(head);
        head = next;
    }
}

A real, easy trap: freeing a node and then reading its ->next pointer is a use-after-free — exactly c2-3's own bug catalog. The next pointer must be saved before the current node is freed, every time.

A Simple Hash Table

An array of "buckets," each bucket its own linked list of key-value pairs, plus a hash function mapping a key to a bucket index.

unsigned int hash(const char *key, int bucket_count) {
    unsigned int h = 5381;
    while (*key) {
        h = h * 33 + *key++;
    }
    return h % bucket_count;
}

Collisions & Separate Chaining

Two keys hashing to the same bucket index don't overwrite each other — they're both appended to that bucket's own linked list, exactly the structure built earlier in this chapter, reused as the collision-handling mechanism itself. Rust's HashMap handles collisions through a much more sophisticated, already-optimized algorithm internally — the programmer never sees or thinks about it at all.

Concept	Rust	C
Growable list	Vec<T> — built in	hand-rolled linked list, or a third-party library
Key-value map	HashMap<K, V> — built in, collisions handled internally	hand-rolled, separate chaining written by hand
Freeing every element	automatic — Drop runs for the whole structure	manual — every single node must be individually freed

Building these once genuinely deepens understanding

Implementing a linked list and a hash table by hand, even once, makes it concretely clear what a "real" library structure like Rust's HashMap is actually doing underneath its convenient interface — not just an abstraction to trust blindly.

Every allocation needs its own free — many nodes means many chances to leak

Freeing only the head pointer, without first freeing every node it originally led to, leaks every one of them — the exact same discipline as c2-2, but now multiplied across potentially many separate allocations instead of just one.

Coding Challenges

Challenge 1

Build a singly linked list by calling push_front three times with different values, print every value by traversing the list, then free the entire list correctly.

📄 View solution

Challenge 2

Rewrite free_list so that it reads head->next AFTER calling free(head) instead of before, deliberately reintroducing the bug the chapter warns about. Explain exactly what goes wrong and why.

📄 View solution

Challenge 3

Explain why separate chaining (appending to a bucket's own linked list) is a workable way to handle two keys that hash to the same bucket index, and what would go wrong if a hash table simply overwrote whatever was already in a bucket instead.

📄 View solution

Chapter 2 Quick Reference

C has no built-in growable list or hash map — every project hand-rolls or imports one
A linked list node is its own heap allocation — one malloc/free pair per node
Always save ->next before calling free on the current node
A hash table is buckets plus a hash function; separate chaining handles collisions by appending to a bucket's own list
Rust's Vec/HashMap provide all of this built in, with collisions and freeing handled automatically
Next chapter: concurrency with pthreads — threads, mutexes, and race conditions