Skip to main content

​
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.

​
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) {
    size_t new_capacity = v->capacity * 2;
    int *new_data = realloc(v->data, new_capacity * sizeof(int));
    if (!new_data) return -1;
    
    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)

#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;
}

#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
static uint64_t hash_string(const char *str) {
    uint64_t hash = 0xcbf29ce484222325ULL;
    while (*str) {
        hash ^= (uint8_t)*str++;
        hash *= 0x100000001b3ULL;
    }
    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) {
    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) {
    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)

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

typedef struct {
    char *buffer;
    size_t capacity;
    size_t head;  // Read position
    size_t tail;  // Write position
} RingBuffer;

RingBuffer *ringbuf_create(size_t capacity) {
    RingBuffer *rb = malloc(sizeof(RingBuffer));
    if (!rb) return NULL;
    
    // Add 1 to distinguish full from empty
    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

1

LRU Cache

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

Red-Black Tree

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

Graph with Adjacency List

Implement a graph with BFS and DFS traversals.
4

Trie

Implement a trie for efficient string prefix matching.

​
Next Up

Undefined Behavior

Understand the dragons lurking in C