Data structures in C

Build linked lists, dynamic arrays, hash tables and binary search trees by hand, and free a whole structure without leaking.

Linked lists and dynamic arrays

Choosing between a linked list and a dynamic array is a memory-layout decision. Arrays win on almost every modern machine because the prefetcher loves contiguous memory; lists win only when you must insert at a known node without shifting.

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

typedef struct Node {
    int          value;
    struct Node *next;        /* complete type needed: use a tag */
} Node;

Node *list_push(Node *head, int value) {
    Node *n = malloc(sizeof *n);
    if (!n) return head;
    n->value = value;
    n->next = head;           /* prepend: O(1) */
    return n;
}

Node *list_reverse(Node *head) {
    Node *prev = NULL;
    while (head) {
        Node *next = head->next;   /* save before overwriting */
        head->next = prev;
        prev = head;
        head = next;
    }
    return prev;
}

void list_free(Node *head) {
    while (head) {
        Node *next = head->next;   /* capture next BEFORE freeing */
        free(head);
        head = next;
    }
}

• Free by walking with a saved next. Calling free(head) first and then reading head->next is a use-after-free.
• A linked list has poor cache locality: each node is a separate allocation, so traversal chases pointers across the heap.
• To delete a node you need the previous node, which is why singly linked lists usually carry a dummy head node in production code.

Hash tables with chaining

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

#define NBUCKETS 1024

typedef struct Entry {
    char         *key;
    int           value;
    struct Entry *next;
} Entry;

typedef struct { Entry *buckets[NBUCKETS]; } Map;

/* FNV-1a: short, fast and good enough for strings */
static uint64_t hash(const char *s) {
    uint64_t h = 1469598103934665603ULL;
    for (; *s; s++) { h ^= (unsigned char)*s; h *= 1099511628211ULL; }
    return h;
}

int map_put(Map *m, const char *key, int value) {
    size_t i = (size_t)(hash(key) % NBUCKETS);
    for (Entry *e = m->buckets[i]; e; e = e->next) {
        if (strcmp(e->key, key) == 0) { e->value = value; return 0; }
    }
    Entry *e = malloc(sizeof *e);
    if (!e) return -1;
    e->key = malloc(strlen(key) + 1);
    if (!e->key) { free(e); return -1; }
    strcpy(e->key, key);
    e->value = value;
    e->next  = m->buckets[i];
    m->buckets[i] = e;
    return 0;
}

int map_get(const Map *m, const char *key, int *out) {
    size_t i = (size_t)(hash(key) % NBUCKETS);
    for (const Entry *e = m->buckets[i]; e; e = e->next)
        if (strcmp(e->key, key) == 0) { *out = e->value; return 0; }
    return -1;      /* not found: do not use 0 as "missing" if 0 is a valid value */
}

void map_free(Map *m) {
    for (size_t i = 0; i < NBUCKETS; i++) {
        Entry *e = m->buckets[i];
        while (e) { Entry *n = e->next; free(e->key); free(e); e = n; }
        m->buckets[i] = NULL;
    }
}

Binary search trees and recursive freeing

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

Tree *tree_insert(Tree *t, int key) {
    if (!t) {
        Tree *n = malloc(sizeof *n);
        if (!n) return NULL;
        n->key = key; n->left = n->right = NULL;
        return n;
    }
    if (key < t->key)      t->left  = tree_insert(t->left,  key);
    else if (key > t->key) t->right = tree_insert(t->right, key);
    return t;
}

int tree_contains(const Tree *t, int key) {
    while (t) {                       /* iterative: no stack growth */
        if (key == t->key) return 1;
        t = key < t->key ? t->left : t->right;
    }
    return 0;
}

/* post-order: children before the parent */
void tree_free(Tree *t) {
    if (!t) return;
    tree_free(t->left);
    tree_free(t->right);
    free(t);
}

For a very deep tree, recursive freeing can exhaust the stack. An iterative free using an explicit stack, or the free-one-rotate-left trick, avoids the recursion entirely.

FAQ

Related

Dynamic memory patterns and allocation bugs Pointers and memory

Last refreshed 2026-09-18.