Why implement data structures from scratch in C?

C's standard library has no containers: no growable arrays, maps or sets. Real C projects either write their own or pull in a library, and writing them yourself teaches memory layout, pointer manipulation and the cost of each operation, which carries over to every other language.

What is a good hash function for strings?

djb2 (h = h * 33 + c, starting from 5381) and FNV-1a are simple, fast and spread typical keys reasonably well. If keys can come from an attacker, use a keyed hash such as SipHash, because a predictable hash lets someone craft many keys that land in the same bucket and slow every lookup to O(n).

When should I use a BST vs a hash table?

Use a hash table for O(1) average lookup when order doesn't matter. Use a binary search tree when you need keys in sorted order, range queries, or the nearest key above or below a value. A plain BST can degrade to O(n) on sorted input, so production code uses a self-balancing variant such as a red-black or AVL tree.

What is a ring buffer?

A ring buffer is a fixed-size array used as a queue, where the head and tail indices wrap around to 0 when they pass the end, using the % operator. Both enqueue and dequeue are O(1) and no element is ever moved. It's the standard structure for bounded queues in drivers, audio pipelines and producer-consumer code.

Data Structures in C | SkillByExample

Stack: Checking Balanced Brackets

A stack is last-in, first-out: you push onto the top and pop from the top. An array plus a top index is all it takes. Matching brackets is the classic use, because the most recent opener must be the first one closed:

#include <stdbool.h>
#include <stdio.h>

#define STACK_MAX 256

typedef struct {
    char data[STACK_MAX];
    int  top;                      /* index of the top item, -1 when empty */
} Stack;

bool push(Stack *s, char c) {
    if (s->top >= STACK_MAX - 1) return false;   /* full */
    s->data[++s->top] = c;
    return true;
}

bool pop(Stack *s, char *out) {
    if (s->top < 0) return false;                /* empty */
    *out = s->data[s->top--];
    return true;
}

bool is_balanced(const char *expr) {
    Stack s = {.top = -1};
    for (const char *p = expr; *p; p++) {
        char open;
        if (*p == '(' || *p == '[' || *p == '{') {
            if (!push(&s, *p)) return false;
        } else if (*p == ')' || *p == ']' || *p == '}') {
            if (!pop(&s, &open)) return false;   /* closer with no opener */
            if ((*p == ')' && open != '(') || (*p == ']' && open != '[') ||
                (*p == '}' && open != '{')) return false;
        }
    }
    return s.top == -1;                          /* leftover openers? */
}

int main(void) {
    const char *tests[] = {"{[()]}", "{[(])}", "((x + y) * z", "a[i] = f(b[j])"};
    for (int i = 0; i < 4; i++)
        printf("%-16s %s\n", tests[i], is_balanced(tests[i]) ? "balanced" : "NOT balanced");
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o stack stack.c
$ ./stack
{[()]}           balanced
{[(])}           NOT balanced
((x + y) * z     NOT balanced
a[i] = f(b[j])   balanced

{[(])} fails at the ]: the top of the stack is (, not [. ((x + y) * z fails at the end because one ( is still on the stack. push and pop return bool rather than crashing on a full or empty stack, and every caller checks the result. bool needs <stdbool.h> in C17. Without it, GCC reports “unknown type name ‘bool’” (C23 makes bool a keyword).

Queue: A Ring Buffer

A queue is first-in, first-out. A fixed array with a head and a tail that wrap around with % gives O(1) operations at both ends without ever moving data:

#include <stdbool.h>
#include <stdio.h>

#define QUEUE_CAP 4

typedef struct {
    int data[QUEUE_CAP];
    int head, tail, size;     /* head: next to dequeue, tail: next free slot */
} Queue;

bool enqueue(Queue *q, int val) {
    if (q->size == QUEUE_CAP) return false;
    q->data[q->tail] = val;
    q->tail = (q->tail + 1) % QUEUE_CAP;    /* wrap around */
    q->size++;
    return true;
}

bool dequeue(Queue *q, int *out) {
    if (q->size == 0) return false;
    *out = q->data[q->head];
    q->head = (q->head + 1) % QUEUE_CAP;
    q->size--;
    return true;
}

int main(void) {
    Queue q = {0};
    int v;
    for (int i = 1; i <= 5; i++)
        printf("enqueue %d: %s\n", i * 10, enqueue(&q, i * 10) ? "ok" : "FULL");
    dequeue(&q, &v); printf("dequeue -> %d\n", v);
    dequeue(&q, &v); printf("dequeue -> %d\n", v);
    enqueue(&q, 50); enqueue(&q, 60);
    printf("head=%d tail=%d size=%d\n", q.head, q.tail, q.size);
    while (dequeue(&q, &v)) printf("%d ", v);
    printf("\n");
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o queue queue.c
$ ./queue
enqueue 10: ok
enqueue 20: ok
enqueue 30: ok
enqueue 40: ok
enqueue 50: FULL
dequeue -> 10
dequeue -> 20
head=2 tail=2 size=4
30 40 50 60

After two dequeues, 50 and 60 went into slots 0 and 1, the space freed at the front of the array, and tail wrapped round to 2. Now head == tail with the queue full, the same index relationship an empty queue has. That’s why the struct keeps a separate size: head and tail alone can’t tell “full” from “empty”. The values still came out in FIFO order, 30 40 50 60.

Hash Tables

A hash function turns a key into a number, and the remainder modulo the table size picks a bucket. Here is djb2 on six names, for an 8-bucket table:

#include <stdio.h>

/* djb2: h = h * 33 + c, starting from 5381 */
unsigned long djb2(const char *s) {
    unsigned long h = 5381;
    for (; *s; s++) h = h * 33 + (unsigned char)*s;
    return h;
}

int main(void) {
    const char *keys[] = {"alice", "bob", "charlie", "dave", "eve", "frank"};
    for (int i = 0; i < 6; i++) {
        unsigned long h = djb2(keys[i]);
        printf("%-8s hash=%-12lu bucket (of 8) = %lu\n", keys[i], h, h % 8);
    }
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o hash hash.c
$ ./hash
alice    hash=210706582979 bucket (of 8) = 3
bob      hash=193487480    bucket (of 8) = 0
charlie  hash=229461886321373 bucket (of 8) = 5
dave     hash=6385144229   bucket (of 8) = 5
eve      hash=193490981    bucket (of 8) = 5
frank    hash=210712719863 bucket (of 8) = 7

Three of the six keys collide in bucket 5. With 6 keys in 8 buckets, collisions are normal rather than a sign of a bad hash (the “birthday problem”). A hash table therefore has to handle them, and separate chaining does it by storing a linked list in each bucket.

A Chained Hash Table

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HT_SIZE 8

typedef struct Entry { char *key; int value; struct Entry *next; } Entry;
typedef struct { Entry *buckets[HT_SIZE]; size_t count; } HashTable;

static size_t bucket_of(const char *s) {
    unsigned long h = 5381;
    for (; *s; s++) h = h * 33 + (unsigned char)*s;
    return h % HT_SIZE;
}

bool ht_set(HashTable *ht, const char *key, int value) {
    Entry **slot = &ht->buckets[bucket_of(key)];
    for (Entry *e = *slot; e; e = e->next)
        if (strcmp(e->key, key) == 0) { e->value = value; return true; }  /* update */
    Entry *e = malloc(sizeof *e);
    if (!e || !(e->key = malloc(strlen(key) + 1))) { free(e); return false; }
    strcpy(e->key, key);
    e->value = value;
    e->next = *slot;                /* new entry goes at the front of the chain */
    *slot = e;
    ht->count++;
    return true;
}

bool ht_get(const HashTable *ht, const char *key, int *out) {
    for (Entry *e = ht->buckets[bucket_of(key)]; e; e = e->next)
        if (strcmp(e->key, key) == 0) { *out = e->value; return true; }
    return false;
}

void ht_free(HashTable *ht) {
    for (size_t i = 0; i < HT_SIZE; i++)
        for (Entry *e = ht->buckets[i], *next; e; e = next) {
            next = e->next;
            free(e->key);
            free(e);
        }
}

int main(void) {
    HashTable ht = {0};
    const char *names[] = {"alice", "bob", "charlie", "dave", "eve", "frank"};
    for (int i = 0; i < 6; i++) ht_set(&ht, names[i], 80 + i);
    ht_set(&ht, "alice", 99);                       /* update, not a new entry */

    int v;
    if (ht_get(&ht, "alice", &v)) printf("alice = %d\n", v);
    if (!ht_get(&ht, "zoe", &v))  printf("zoe not found\n");
    printf("count = %zu\n", ht.count);
    for (size_t i = 0; i < HT_SIZE; i++) {
        printf("bucket %zu:", i);
        for (Entry *e = ht.buckets[i]; e; e = e->next) printf(" %s", e->key);
        printf("\n");
    }
    ht_free(&ht);
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o hashtable hashtable.c
$ ./hashtable
alice = 99
zoe not found
count = 6
bucket 0: bob
bucket 1:
bucket 2:
bucket 3: alice
bucket 4:
bucket 5: eve dave charlie
bucket 6:
bucket 7: frank

The bucket dump matches the hash output above, and bucket 5 holds its three keys as a chain. They appear in reverse insertion order because new entries go at the front, which is O(1). Setting alice a second time updated the value in place, so count stayed at 6. The table copies each key into memory it owns, using malloc + strcpy rather than strdup, which isn’t declared under strict -std=c17. That way callers can pass temporary strings safely, and ht_free releases the keys along with the entries. A real table also tracks its load factor (count / HT_SIZE) and resizes before chains get long.

Binary Search Trees

In a BST, every key in a node’s left subtree is smaller than the node’s key, and every key in its right subtree is larger. An in-order walk (left, node, right) therefore visits the keys in sorted order. But the shape of the tree depends on the order of insertion:

#include <stdio.h>
#include <stdlib.h>

typedef struct BST { int key; struct BST *left, *right; } BST;

BST *bst_insert(BST *root, int key) {
    if (!root) {
        BST *n = malloc(sizeof *n);
        if (!n) exit(1);
        *n = (BST){key, NULL, NULL};
        return n;
    }
    if (key < root->key)      root->left  = bst_insert(root->left, key);
    else if (key > root->key) root->right = bst_insert(root->right, key);
    return root;                               /* duplicates are ignored */
}

void bst_inorder(const BST *root) {            /* left, node, right = sorted */
    if (!root) return;
    bst_inorder(root->left);
    printf("%d ", root->key);
    bst_inorder(root->right);
}

int bst_height(const BST *root) {
    if (!root) return 0;
    int l = bst_height(root->left), r = bst_height(root->right);
    return 1 + (l > r ? l : r);
}

void bst_free(BST *root) {
    if (!root) return;
    bst_free(root->left);
    bst_free(root->right);
    free(root);
}

int main(void) {
    int mixed[] = {5, 3, 7, 1, 4, 6, 8}, sorted[] = {1, 3, 4, 5, 6, 7, 8};
    BST *a = NULL, *b = NULL;
    for (int i = 0; i < 7; i++) { a = bst_insert(a, mixed[i]); b = bst_insert(b, sorted[i]); }
    printf("mixed order:  "); bst_inorder(a); printf(" height %d\n", bst_height(a));
    printf("sorted order: "); bst_inorder(b); printf(" height %d\n", bst_height(b));
    bst_free(a);
    bst_free(b);
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o bst bst.c
$ ./bst
mixed order:  1 3 4 5 6 7 8  height 3
sorted order: 1 3 4 5 6 7 8  height 7

The same seven keys produce the same sorted walk, but very different trees. Inserted in mixed order, they form a perfectly balanced tree of height 3, so any search takes at most 3 comparisons. Inserted already sorted, every key goes to the right of the previous one, and the “tree” is really a linked list of height 7. Search then degrades from O(log n) to O(n). This is why production code uses self-balancing trees (red-black, AVL), which restructure themselves on insert.

Deleting from a BST

Deletion has three cases, depending on how many children the doomed node has:

#include <stdio.h>
#include <stdlib.h>

typedef struct BST { int key; struct BST *left, *right; } BST;

BST *bst_insert(BST *root, int key) {
    if (!root) {
        BST *n = malloc(sizeof *n);
        if (!n) exit(1);
        *n = (BST){key, NULL, NULL};
        return n;
    }
    if (key < root->key)      root->left  = bst_insert(root->left, key);
    else if (key > root->key) root->right = bst_insert(root->right, key);
    return root;
}

BST *bst_delete(BST *root, int key) {
    if (!root) return NULL;
    if (key < root->key)      root->left  = bst_delete(root->left, key);
    else if (key > root->key) root->right = bst_delete(root->right, key);
    else if (!root->left || !root->right) {   /* zero or one child */
        BST *child = root->left ? root->left : root->right;
        free(root);
        return child;
    } else {                                  /* two children */
        BST *succ = root->right;
        while (succ->left) succ = succ->left; /* smallest key on the right */
        root->key = succ->key;
        root->right = bst_delete(root->right, succ->key);
    }
    return root;
}

void inorder(const BST *r) {
    if (r) { inorder(r->left); printf(" %d", r->key); inorder(r->right); }
}

void show(const char *label, const BST *root) {
    printf("%s root=%s ", label, root ? "" : "(empty)");
    if (root) printf("%d", root->key);
    printf(" |");
    inorder(root);
    printf("\n");
}

int main(void) {
    int keys[] = {5, 3, 7, 1, 4, 6, 8};
    BST *t = NULL;
    for (int i = 0; i < 7; i++) t = bst_insert(t, keys[i]);
    show("start:        ", t);
    t = bst_delete(t, 1); show("delete 1 leaf:", t);
    t = bst_delete(t, 3); show("delete 3 one: ", t);
    t = bst_delete(t, 5); show("delete 5 root:", t);
    while (t) t = bst_delete(t, t->key);
    show("delete all:   ", t);
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o bstdelete bstdelete.c
$ ./bstdelete
start:         root= 5 | 1 3 4 5 6 7 8
delete 1 leaf: root= 5 | 3 4 5 6 7 8
delete 3 one:  root= 5 | 4 5 6 7 8
delete 5 root: root= 6 | 4 6 7 8
delete all:    root=(empty)  |

A leaf (1) is simply removed. A node with one child (3, which had only 4 left after 1 went) is replaced by that child. A node with two children (the root, 5) can’t be removed directly, so it takes the key of its in-order successor, the smallest key in its right subtree (6). That successor, which has at most one child, is then deleted from the right subtree instead. The in-order walk stays sorted after every step. Draining the tree to (empty) with no ASan report confirms that every node was freed exactly once.

Practice

Use a stack to reverse the string "stressed".

Solution

#include <stdio.h>
#include <string.h>

int main(void) {
    const char *word = "stressed";
    char stack[64];
    int top = -1;
    for (size_t i = 0; i < strlen(word); i++) stack[++top] = word[i];   /* push */
    while (top >= 0) putchar(stack[top--]);                            /* pop */
    putchar('\n');
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o p1 p1.c
$ ./p1
desserts

Pushing puts the characters in; popping takes them out last-first, which reverses them. The recursion in the BST code relies on the same property of the call stack: whatever was entered last is finished first.

Count word frequencies in "the cat and the hat and the bat" with a chained hash table.

Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define HT_SIZE 16
typedef struct Entry { char *word; int count; struct Entry *next; } Entry;

static size_t bucket_of(const char *s) {
    unsigned long h = 5381;
    for (; *s; s++) h = h * 33 + (unsigned char)*s;
    return h % HT_SIZE;
}

void count_word(Entry **table, const char *w) {
    Entry **slot = &table[bucket_of(w)];
    for (Entry *e = *slot; e; e = e->next)
        if (strcmp(e->word, w) == 0) { e->count++; return; }
    Entry *e = malloc(sizeof *e);
    e->word = malloc(strlen(w) + 1);
    strcpy(e->word, w);
    e->count = 1;
    e->next = *slot;
    *slot = e;
}

int main(void) {
    char text[] = "the cat and the hat and the bat";
    Entry *table[HT_SIZE] = {0};
    for (char *w = strtok(text, " "); w; w = strtok(NULL, " ")) count_word(table, w);
    for (size_t i = 0; i < HT_SIZE; i++)
        for (Entry *e = table[i], *next; e; e = next) {
            printf("%-4s %d\n", e->word, e->count);
            next = e->next;
            free(e->word);
            free(e);
        }
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o p2 p2.c
$ ./p2
hat  1
the  3
and  2
bat  1
cat  1

The words come out in bucket order, not the order they appeared: a hash table has no inherent ordering. To print them alphabetically you’d copy the entries into an array and qsort it, or store them in a BST instead. (The malloc results are unchecked here to keep the exercise short.)

Write count_in_range(root, lo, hi) for a BST that skips any subtree that can’t contain keys in [lo, hi].

Solution

#include <stdio.h>
#include <stdlib.h>

typedef struct BST { int key; struct BST *left, *right; } BST;

BST *bst_insert(BST *root, int key) {
    if (!root) {
        BST *n = malloc(sizeof *n);
        *n = (BST){key, NULL, NULL};
        return n;
    }
    if (key < root->key)      root->left  = bst_insert(root->left, key);
    else if (key > root->key) root->right = bst_insert(root->right, key);
    return root;
}

int count_in_range(const BST *root, int lo, int hi) {
    if (!root) return 0;
    if (root->key < lo) return count_in_range(root->right, lo, hi);   /* skip left */
    if (root->key > hi) return count_in_range(root->left, lo, hi);    /* skip right */
    return 1 + count_in_range(root->left, lo, hi) + count_in_range(root->right, lo, hi);
}

void bst_free(BST *r) { if (r) { bst_free(r->left); bst_free(r->right); free(r); } }

int main(void) {
    int keys[] = {50, 30, 70, 20, 40, 60, 80, 35, 65};
    BST *t = NULL;
    for (int i = 0; i < 9; i++) t = bst_insert(t, keys[i]);
    printf("keys in [35, 65]: %d\n", count_in_range(t, 35, 65));
    printf("keys in [0, 25]:  %d\n", count_in_range(t, 0, 25));
    bst_free(t);
    return 0;
}

$ gcc -Wall -Wextra -std=c17 -g -fsanitize=address,undefined -o p3 p3.c
$ ./p3
keys in [35, 65]: 5
keys in [0, 25]:  1

The five keys in range are 35, 40, 50, 60 and 65. When a node is below lo, its entire left subtree is smaller still and is skipped without being visited. This kind of range query is something a hash table can’t do efficiently.

In the queue example, change QUEUE_CAP to 8 and re-run it. Which lines change, and why?

Solution

$ gcc -Wall -Wextra -std=c17 -o q8 q8.c
$ ./q8
enqueue 10: ok
enqueue 20: ok
enqueue 30: ok
enqueue 40: ok
enqueue 50: ok
dequeue -> 10
dequeue -> 20
head=2 tail=7 size=5
30 40 50 50 60

With room for 8, the fifth enqueue succeeds, and 50 ends up in the queue twice (once from the loop, once afterwards). No wraparound happens either: tail just advances to 7. The bigger capacity hides the wraparound code path entirely, which is why ring-buffer tests deliberately use a tiny capacity.

Stack: Checking Balanced Brackets

Queue: A Ring Buffer

Hash Tables

A Chained Hash Table

Binary Search Trees

Deleting from a BST

Practice

Frequently Asked Questions