Data Structures in C

Building data structures in C teaches you exactly how computers work with data. No magic, no hidden allocation — just pure memory manipulation. In languages like Python or Java, list.append(x) hides a cascade of decisions: Should we resize? How much? Where does the old memory go? In C, you make every one of those decisions yourself. That is both the burden and the superpower.

Dynamic Array (Vector)

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

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} Vector;

Vector *vector_create(size_t initial_capacity) {
    Vector *v = malloc(sizeof(Vector));
    if (!v) return NULL;
    
    v->data = malloc(initial_capacity * sizeof(int));
    if (!v->data) {
        free(v);
        return NULL;
    }
    
    v->size = 0;
    v->capacity = initial_capacity;
    return v;
}

void vector_destroy(Vector *v) {
    if (v) {
        free(v->data);
        free(v);
    }
}

static int vector_grow(Vector *v) {
    // Double the capacity each time. This gives amortized O(1) push -- you pay
    // for an expensive copy occasionally, but averaged over N pushes, each push
    // costs O(1). Growing by a constant amount (e.g., +10) would be O(N) per push.
    size_t new_capacity = v->capacity * 2;
    
    // realloc may move the entire block to a new address if it cannot extend
    // in-place. After this call, ALL old pointers into v->data are invalid.
    // This is a common source of use-after-free bugs when external code caches
    // pointers into the vector's internal array.
    int *new_data = realloc(v->data, new_capacity * sizeof(int));
    if (!new_data) return -1;  // Original v->data is still valid on failure
    
    v->data = new_data;
    v->capacity = new_capacity;
    return 0;
}

int vector_push(Vector *v, int value) {
    if (v->size == v->capacity) {
        if (vector_grow(v) != 0) return -1;
    }
    v->data[v->size++] = value;
    return 0;
}

int vector_pop(Vector *v) {
    if (v->size == 0) {
        return 0;  // Or handle error
    }
    return v->data[--v->size];
}

int vector_get(Vector *v, size_t index) {
    if (index >= v->size) {
        return 0;  // Or handle error
    }
    return v->data[index];
}

void vector_set(Vector *v, size_t index, int value) {
    if (index < v->size) {
        v->data[index] = value;
    }
}

// Usage
int main(void) {
    Vector *v = vector_create(4);
    
    for (int i = 0; i < 20; i++) {
        vector_push(v, i * 10);
    }
    
    for (size_t i = 0; i < v->size; i++) {
        printf("%d ", vector_get(v, i));
    }
    printf("\n");
    
    vector_destroy(v);
    return 0;
}

Linked List

Singly Linked List

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

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

typedef struct {
    Node *head;
    Node *tail;
    size_t size;
} LinkedList;

LinkedList *list_create(void) {
    LinkedList *list = calloc(1, sizeof(LinkedList));
    return list;
}

void list_destroy(LinkedList *list) {
    Node *current = list->head;
    while (current) {
        Node *next = current->next;
        free(current);
        current = next;
    }
    free(list);
}

int list_push_front(LinkedList *list, int value) {
    Node *node = malloc(sizeof(Node));
    if (!node) return -1;
    
    node->data = value;
    node->next = list->head;
    list->head = node;
    
    if (!list->tail) {
        list->tail = node;
    }
    
    list->size++;
    return 0;
}

int list_push_back(LinkedList *list, int value) {
    Node *node = malloc(sizeof(Node));
    if (!node) return -1;
    
    node->data = value;
    node->next = NULL;
    
    if (list->tail) {
        list->tail->next = node;
    } else {
        list->head = node;
    }
    list->tail = node;
    
    list->size++;
    return 0;
}

int list_pop_front(LinkedList *list) {
    if (!list->head) return 0;
    
    Node *old_head = list->head;
    int value = old_head->data;
    
    list->head = old_head->next;
    if (!list->head) {
        list->tail = NULL;
    }
    
    free(old_head);
    list->size--;
    return value;
}

void list_print(LinkedList *list) {
    for (Node *n = list->head; n; n = n->next) {
        printf("%d -> ", n->data);
    }
    printf("NULL\n");
}

Intrusive Linked List (Linux Kernel Style)

In a normal linked list, the node struct wraps the data (struct Node { int data; Node *next; }). In an intrusive list, you do the opposite: you embed the list linkage inside your data structure. This is how the Linux kernel manages almost everything — process lists, file system entries, driver queues. The key advantage: zero extra allocations (the node lives inside the object), and one object can be on multiple lists simultaneously by embedding multiple list_head fields.

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

// The list node is embedded in your structure
typedef struct list_head {
    struct list_head *next;
    struct list_head *prev;
} list_head;

#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) list_head name = LIST_HEAD_INIT(name)

static inline void INIT_LIST_HEAD(list_head *list) {
    list->next = list;
    list->prev = list;
}

static inline void list_add(list_head *new, list_head *head) {
    head->next->prev = new;
    new->next = head->next;
    new->prev = head;
    head->next = new;
}

static inline void list_del(list_head *entry) {
    entry->prev->next = entry->next;
    entry->next->prev = entry->prev;
}

static inline int list_empty(const list_head *head) {
    return head->next == head;
}

// container_of: Given a pointer to a list_head member inside a struct,
// recover the pointer to the enclosing struct. This is the magic behind
// intrusive lists. It works by subtracting the member's offset from the
// member's address, which gives you the base address of the containing struct.
// Example: if Task.list is at offset 36, and we have a list_head* at 0x1024,
// then the Task* is at 0x1024 - 36 = 0x1000.
#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

#define list_for_each(pos, head) \
    for (pos = (head)->next; pos != (head); pos = pos->next)

#define list_for_each_entry(pos, head, member) \
    for (pos = list_entry((head)->next, typeof(*pos), member); \
         &pos->member != (head); \
         pos = list_entry(pos->member.next, typeof(*pos), member))

// Usage
typedef struct {
    int id;
    char name[32];
    list_head list;  // Embed the list node
} Task;

int main(void) {
    LIST_HEAD(task_list);
    
    // Add tasks
    for (int i = 0; i < 5; i++) {
        Task *t = malloc(sizeof(Task));
        t->id = i;
        snprintf(t->name, sizeof(t->name), "Task %d", i);
        list_add(&t->list, &task_list);
    }
    
    // Iterate
    Task *task;
    list_for_each_entry(task, &task_list, list) {
        printf("Task: %d - %s\n", task->id, task->name);
    }
    
    // Cleanup (in real code, be more careful)
    list_head *pos, *tmp;
    for (pos = task_list.next; pos != &task_list; ) {
        tmp = pos->next;
        Task *t = list_entry(pos, Task, list);
        list_del(pos);
        free(t);
        pos = tmp;
    }
    
    return 0;
}

Hash Table

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

#define INITIAL_CAPACITY 16
#define LOAD_FACTOR 0.75

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

typedef struct {
    Entry **buckets;
    size_t capacity;
    size_t size;
} HashMap;

// FNV-1a hash: A simple, fast, non-cryptographic hash function with good
// distribution properties. The magic constants are carefully chosen primes.
// NEVER use this (or any non-cryptographic hash) for security-sensitive purposes
// like password hashing or hash tables exposed to adversarial input -- an
// attacker can craft keys that all collide, turning O(1) lookups into O(n).
static uint64_t hash_string(const char *str) {
    uint64_t hash = 0xcbf29ce484222325ULL;  // FNV offset basis
    while (*str) {
        hash ^= (uint8_t)*str++;
        hash *= 0x100000001b3ULL;  // FNV prime
    }
    return hash;
}

HashMap *hashmap_create(void) {
    HashMap *map = malloc(sizeof(HashMap));
    if (!map) return NULL;
    
    map->buckets = calloc(INITIAL_CAPACITY, sizeof(Entry*));
    if (!map->buckets) {
        free(map);
        return NULL;
    }
    
    map->capacity = INITIAL_CAPACITY;
    map->size = 0;
    return map;
}

void hashmap_destroy(HashMap *map) {
    for (size_t i = 0; i < map->capacity; i++) {
        Entry *e = map->buckets[i];
        while (e) {
            Entry *next = e->next;
            free(e->key);
            free(e);
            e = next;
        }
    }
    free(map->buckets);
    free(map);
}

static int hashmap_resize(HashMap *map) {
    size_t new_capacity = map->capacity * 2;
    Entry **new_buckets = calloc(new_capacity, sizeof(Entry*));
    if (!new_buckets) return -1;
    
    // Rehash all entries
    for (size_t i = 0; i < map->capacity; i++) {
        Entry *e = map->buckets[i];
        while (e) {
            Entry *next = e->next;
            size_t new_index = hash_string(e->key) % new_capacity;
            e->next = new_buckets[new_index];
            new_buckets[new_index] = e;
            e = next;
        }
    }
    
    free(map->buckets);
    map->buckets = new_buckets;
    map->capacity = new_capacity;
    return 0;
}

int hashmap_put(HashMap *map, const char *key, int value) {
    // When the load factor exceeds 0.75, resize to keep average chain length
    // short. Without resizing, lookup degrades from O(1) to O(n) as chains grow.
    // The 0.75 threshold is a well-studied sweet spot: lower wastes memory,
    // higher increases collision rates.
    if ((double)map->size / map->capacity > LOAD_FACTOR) {
        if (hashmap_resize(map) != 0) return -1;
    }
    
    size_t index = hash_string(key) % map->capacity;
    
    // Check for existing key
    for (Entry *e = map->buckets[index]; e; e = e->next) {
        if (strcmp(e->key, key) == 0) {
            e->value = value;
            return 0;
        }
    }
    
    // New entry
    Entry *entry = malloc(sizeof(Entry));
    if (!entry) return -1;
    
    entry->key = strdup(key);
    if (!entry->key) {
        free(entry);
        return -1;
    }
    
    entry->value = value;
    entry->next = map->buckets[index];
    map->buckets[index] = entry;
    map->size++;
    
    return 0;
}

int hashmap_get(HashMap *map, const char *key, int *value) {
    size_t index = hash_string(key) % map->capacity;
    
    for (Entry *e = map->buckets[index]; e; e = e->next) {
        if (strcmp(e->key, key) == 0) {
            *value = e->value;
            return 1;  // Found
        }
    }
    
    return 0;  // Not found
}

int hashmap_remove(HashMap *map, const char *key) {
    size_t index = hash_string(key) % map->capacity;
    
    Entry *prev = NULL;
    Entry *e = map->buckets[index];
    
    while (e) {
        if (strcmp(e->key, key) == 0) {
            if (prev) {
                prev->next = e->next;
            } else {
                map->buckets[index] = e->next;
            }
            free(e->key);
            free(e);
            map->size--;
            return 1;
        }
        prev = e;
        e = e->next;
    }
    
    return 0;
}

Binary Search Tree

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

typedef struct TreeNode {
    int key;
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

typedef struct {
    TreeNode *root;
    size_t size;
} BST;

BST *bst_create(void) {
    return calloc(1, sizeof(BST));
}

static void bst_destroy_node(TreeNode *node) {
    if (node) {
        bst_destroy_node(node->left);
        bst_destroy_node(node->right);
        free(node);
    }
}

void bst_destroy(BST *tree) {
    bst_destroy_node(tree->root);
    free(tree);
}

static TreeNode *create_node(int key, int value) {
    TreeNode *node = malloc(sizeof(TreeNode));
    if (node) {
        node->key = key;
        node->value = value;
        node->left = node->right = NULL;
    }
    return node;
}

int bst_insert(BST *tree, int key, int value) {
    // The pointer-to-pointer technique: instead of tracking a "parent" node,
    // we hold a pointer to the pointer that needs to be updated. This elegantly
    // handles both the "tree is empty" case (current = &tree->root) and the
    // "insert as child" case (current = &node->left or &node->right) with
    // identical code. Linus Torvalds famously cited this pattern as the mark
    // of someone who truly understands pointers.
    TreeNode **current = &tree->root;
    
    while (*current) {
        if (key < (*current)->key) {
            current = &(*current)->left;
        } else if (key > (*current)->key) {
            current = &(*current)->right;
        } else {
            // Key exists, update value
            (*current)->value = value;
            return 0;
        }
    }
    
    *current = create_node(key, value);
    if (!*current) return -1;
    
    tree->size++;
    return 0;
}

int bst_find(BST *tree, int key, int *value) {
    TreeNode *current = tree->root;
    
    while (current) {
        if (key < current->key) {
            current = current->left;
        } else if (key > current->key) {
            current = current->right;
        } else {
            *value = current->value;
            return 1;
        }
    }
    
    return 0;
}

static TreeNode *find_min(TreeNode *node) {
    while (node->left) {
        node = node->left;
    }
    return node;
}

static TreeNode *bst_remove_node(TreeNode *node, int key, int *removed) {
    if (!node) return NULL;
    
    if (key < node->key) {
        node->left = bst_remove_node(node->left, key, removed);
    } else if (key > node->key) {
        node->right = bst_remove_node(node->right, key, removed);
    } else {
        *removed = 1;
        
        if (!node->left) {
            TreeNode *right = node->right;
            free(node);
            return right;
        }
        if (!node->right) {
            TreeNode *left = node->left;
            free(node);
            return left;
        }
        
        // Two children: find inorder successor
        TreeNode *successor = find_min(node->right);
        node->key = successor->key;
        node->value = successor->value;
        node->right = bst_remove_node(node->right, successor->key, removed);
    }
    
    return node;
}

int bst_remove(BST *tree, int key) {
    int removed = 0;
    tree->root = bst_remove_node(tree->root, key, &removed);
    if (removed) tree->size--;
    return removed;
}

// Traversals
void bst_inorder(TreeNode *node, void (*visit)(int, int)) {
    if (node) {
        bst_inorder(node->left, visit);
        visit(node->key, node->value);
        bst_inorder(node->right, visit);
    }
}

Min Heap (Priority Queue)

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

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} MinHeap;

MinHeap *heap_create(size_t capacity) {
    MinHeap *h = malloc(sizeof(MinHeap));
    if (!h) return NULL;
    
    h->data = malloc(capacity * sizeof(int));
    if (!h->data) {
        free(h);
        return NULL;
    }
    
    h->size = 0;
    h->capacity = capacity;
    return h;
}

void heap_destroy(MinHeap *h) {
    if (h) {
        free(h->data);
        free(h);
    }
}

static void swap(int *a, int *b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

static void sift_up(MinHeap *h, size_t index) {
    while (index > 0) {
        size_t parent = (index - 1) / 2;
        if (h->data[index] >= h->data[parent]) break;
        swap(&h->data[index], &h->data[parent]);
        index = parent;
    }
}

static void sift_down(MinHeap *h, size_t index) {
    while (1) {
        size_t smallest = index;
        size_t left = 2 * index + 1;
        size_t right = 2 * index + 2;
        
        if (left < h->size && h->data[left] < h->data[smallest]) {
            smallest = left;
        }
        if (right < h->size && h->data[right] < h->data[smallest]) {
            smallest = right;
        }
        
        if (smallest == index) break;
        
        swap(&h->data[index], &h->data[smallest]);
        index = smallest;
    }
}

int heap_push(MinHeap *h, int value) {
    if (h->size == h->capacity) {
        size_t new_cap = h->capacity * 2;
        int *new_data = realloc(h->data, new_cap * sizeof(int));
        if (!new_data) return -1;
        h->data = new_data;
        h->capacity = new_cap;
    }
    
    h->data[h->size] = value;
    sift_up(h, h->size);
    h->size++;
    return 0;
}

int heap_pop(MinHeap *h) {
    if (h->size == 0) return 0;  // Or error
    
    int min = h->data[0];
    h->data[0] = h->data[--h->size];
    if (h->size > 0) {
        sift_down(h, 0);
    }
    return min;
}

int heap_peek(MinHeap *h) {
    return h->size > 0 ? h->data[0] : 0;
}

Ring Buffer (Circular Queue)

A ring buffer is one of the most important data structures in systems programming. It appears everywhere: UART receive buffers in embedded systems, audio sample buffers, network packet queues, and the Linux kernel’s kfifo. The key insight is that both the producer and consumer only move forward — the buffer wraps around using modular arithmetic, so it reuses memory without any allocation or copying.

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

typedef struct {
    char *buffer;
    size_t capacity;
    size_t head;  // Read position (consumer advances this)
    size_t tail;  // Write position (producer advances this)
} RingBuffer;

RingBuffer *ringbuf_create(size_t capacity) {
    RingBuffer *rb = malloc(sizeof(RingBuffer));
    if (!rb) return NULL;
    
    // Allocate one extra slot to distinguish "full" from "empty."
    // Without this trick, head == tail means both "empty" and "full,"
    // which is ambiguous. By wasting one slot, full is when
    // (tail + 1) % capacity == head, and empty is head == tail.
    rb->buffer = malloc(capacity + 1);
    if (!rb->buffer) {
        free(rb);
        return NULL;
    }
    
    rb->capacity = capacity + 1;
    rb->head = 0;
    rb->tail = 0;
    return rb;
}

void ringbuf_destroy(RingBuffer *rb) {
    if (rb) {
        free(rb->buffer);
        free(rb);
    }
}

bool ringbuf_is_empty(RingBuffer *rb) {
    return rb->head == rb->tail;
}

bool ringbuf_is_full(RingBuffer *rb) {
    return ((rb->tail + 1) % rb->capacity) == rb->head;
}

size_t ringbuf_size(RingBuffer *rb) {
    if (rb->tail >= rb->head) {
        return rb->tail - rb->head;
    }
    return rb->capacity - rb->head + rb->tail;
}

size_t ringbuf_write(RingBuffer *rb, const char *data, size_t len) {
    size_t written = 0;
    
    while (written < len && !ringbuf_is_full(rb)) {
        rb->buffer[rb->tail] = data[written++];
        rb->tail = (rb->tail + 1) % rb->capacity;
    }
    
    return written;
}

size_t ringbuf_read(RingBuffer *rb, char *data, size_t len) {
    size_t read = 0;
    
    while (read < len && !ringbuf_is_empty(rb)) {
        data[read++] = rb->buffer[rb->head];
        rb->head = (rb->head + 1) % rb->capacity;
    }
    
    return read;
}

// Lock-free single producer, single consumer variant
typedef struct {
    char *buffer;
    size_t capacity;
    _Atomic size_t head;
    _Atomic size_t tail;
} LockFreeRingBuffer;

Generic Data Structure with void*

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

typedef int (*CompareFunc)(const void*, const void*);
typedef void (*FreeFunc)(void*);
typedef void (*PrintFunc)(const void*);

typedef struct {
    void **data;
    size_t size;
    size_t capacity;
    size_t elem_size;
    CompareFunc compare;
    FreeFunc free_elem;
} GenericVector;

GenericVector *gvec_create(size_t elem_size, size_t initial_cap,
                           CompareFunc cmp, FreeFunc free_fn) {
    GenericVector *v = malloc(sizeof(GenericVector));
    if (!v) return NULL;
    
    v->data = malloc(initial_cap * sizeof(void*));
    if (!v->data) {
        free(v);
        return NULL;
    }
    
    v->size = 0;
    v->capacity = initial_cap;
    v->elem_size = elem_size;
    v->compare = cmp;
    v->free_elem = free_fn;
    
    return v;
}

void gvec_destroy(GenericVector *v) {
    if (v) {
        if (v->free_elem) {
            for (size_t i = 0; i < v->size; i++) {
                v->free_elem(v->data[i]);
            }
        }
        free(v->data);
        free(v);
    }
}

int gvec_push(GenericVector *v, const void *elem) {
    if (v->size == v->capacity) {
        size_t new_cap = v->capacity * 2;
        void **new_data = realloc(v->data, new_cap * sizeof(void*));
        if (!new_data) return -1;
        v->data = new_data;
        v->capacity = new_cap;
    }
    
    v->data[v->size] = malloc(v->elem_size);
    if (!v->data[v->size]) return -1;
    
    memcpy(v->data[v->size], elem, v->elem_size);
    v->size++;
    return 0;
}

void *gvec_get(GenericVector *v, size_t index) {
    if (index >= v->size) return NULL;
    return v->data[index];
}

// Usage with different types
typedef struct {
    char name[50];
    int age;
} Person;

int compare_person(const void *a, const void *b) {
    return strcmp(((Person*)a)->name, ((Person*)b)->name);
}

void print_person(const void *p) {
    const Person *person = p;
    printf("%s (%d)\n", person->name, person->age);
}

int main(void) {
    GenericVector *people = gvec_create(sizeof(Person), 10,
                                         compare_person, free);
    
    Person p1 = {"Alice", 30};
    Person p2 = {"Bob", 25};
    
    gvec_push(people, &p1);
    gvec_push(people, &p2);
    
    for (size_t i = 0; i < people->size; i++) {
        print_person(gvec_get(people, i));
    }
    
    gvec_destroy(people);
    return 0;
}

Exercises

LRU Cache

Implement an LRU cache using a hash map and doubly linked list.

Red-Black Tree

Implement a self-balancing red-black tree with insert and delete.

Graph with Adjacency List

Implement a graph with BFS and DFS traversals.

Trie

Implement a trie for efficient string prefix matching.

Next Up

Undefined Behavior

Understand the dragons lurking in C

​Data Structures in C

​Dynamic Array (Vector)

​Linked List

​Singly Linked List

​Intrusive Linked List (Linux Kernel Style)

​Hash Table

​Binary Search Tree

​Min Heap (Priority Queue)

​Ring Buffer (Circular Queue)

​Generic Data Structure with void*

​Exercises

​Next Up