18. Data structures from scratch: linked lists, stacks/queues, hash tables, trees

18.1 Singly linked list

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

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

Node *node_new(int value) {
    Node *n = malloc(sizeof(Node));
    if (!n) return NULL;
    n->value = value;
    n->next = NULL;
    return n;
}

int list_push_front(Node **head, int value) {
    Node *n = node_new(value);
    if (!n) return 0;
    n->next = *head;
    *head = n;             // pointer-to-pointer: rewrites the caller's head
    return 1;
}

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

int main(void) {
    Node *head = NULL;
    for (int i = 1; i <= 5; i++) {
        if (!list_push_front(&head, i)) { perror("malloc"); list_free(head); return 1; }
    }
    for (Node *n = head; n; n = n->next) printf("%d ", n->value);
    printf("\n");
    list_free(head);
    return 0;
}

18.2 A real hash table (separate chaining, djb2 hash)

// hashtable.h/.c — string-keyed hash table with chaining
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct HTEntry {
    char *key;
    int   value;
    struct HTEntry *next;   // chain for collisions
} HTEntry;

typedef struct {
    HTEntry **buckets;
    size_t    num_buckets;
    size_t    count;
} HashTable;

static unsigned long djb2(const char *s) {
    unsigned long hash = 5381;
    int c;
    while ((c = (unsigned char)*s++)) hash = ((hash << 5) + hash) + (unsigned long)c; // hash*33 + c
    return hash;
}

static char *xstrdup(const char *s) {
    size_t len = strlen(s) + 1;
    char *copy = malloc(len);
    if (!copy) return NULL;
    memcpy(copy, s, len);
    return copy;
}

HashTable *ht_new(size_t num_buckets) {
    if (num_buckets == 0) return NULL;
    HashTable *ht = malloc(sizeof(HashTable));
    if (!ht) return NULL;
    ht->buckets = calloc(num_buckets, sizeof(HTEntry *));
    if (!ht->buckets) { free(ht); return NULL; }
    ht->num_buckets = num_buckets;
    ht->count = 0;
    return ht;
}

int ht_set(HashTable *ht, const char *key, int value) {
    unsigned long idx = djb2(key) % ht->num_buckets;
    for (HTEntry *e = ht->buckets[idx]; e; e = e->next) {
        if (strcmp(e->key, key) == 0) { e->value = value; return 1; }  // update existing
    }
    HTEntry *e = malloc(sizeof(HTEntry));
    if (!e) return 0;
    e->key = xstrdup(key);
    if (!e->key) { free(e); return 0; }
    e->value = value;
    e->next = ht->buckets[idx];   // insert at head of chain
    ht->buckets[idx] = e;
    ht->count++;
    return 1;
}

int ht_get(HashTable *ht, const char *key, int *out) {
    unsigned long idx = djb2(key) % ht->num_buckets;
    for (HTEntry *e = ht->buckets[idx]; e; e = e->next) {
        if (strcmp(e->key, key) == 0) { *out = e->value; return 1; }
    }
    return 0;
}

void ht_free(HashTable *ht) {
    if (!ht) return;
    for (size_t i = 0; i < ht->num_buckets; i++) {
        HTEntry *e = ht->buckets[i];
        while (e) { HTEntry *next = e->next; free(e->key); free(e); e = next; }
    }
    free(ht->buckets);
    free(ht);
}

int main(void) {
    HashTable *ht = ht_new(16);
    if (!ht) { perror("ht_new"); return 1; }
    if (!ht_set(ht, "apples", 5) ||
        !ht_set(ht, "oranges", 3) ||
        !ht_set(ht, "apples", 7)) {   // update
        perror("ht_set");
        ht_free(ht);
        return 1;
    }

    int v;
    if (ht_get(ht, "apples", &v)) printf("apples = %d\n", v);   // 7
    if (!ht_get(ht, "bananas", &v)) printf("bananas not found\n");

    ht_free(ht);
    return 0;
}

djb2 (Dan Bernstein's hash) is real, used-in-production code — a version of it or FNV-1a appears in countless small C libraries because it's a handful of lines and good enough for non-adversarial keys. Real-world example. For untrusted keys (e.g., HTTP header names from the network), a predictable hash lets an attacker force worst-case O(n) chains — a real DoS class called "hash flooding" (behind CVE-2011-4815 and similar). Production hash tables (Python's dict, Redis's dict) seed the hash randomly per-process specifically to prevent this.

18.3 A binary search tree, for completeness

typedef struct BSTNode {
    int value;
    struct BSTNode *left, *right;
} BSTNode;

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

void bst_inorder(BSTNode *root, void (*visit)(int)) {
    if (!root) return;
    bst_inorder(root->left, visit);
    visit(root->value);
    bst_inorder(root->right, visit);
}