Data Structures in C

Stack (Array-Based)

A stack is a last-in, first-out (LIFO) data structure. The last item pushed is the first item popped. Stacks are fundamental to expression evaluation, function call management (the call stack is itself a stack), undo systems, and depth-first search. An array-based implementation is simple and cache-friendly.

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

#define STACK_MAX 256

typedef struct {
    int  data[STACK_MAX];
    int  top;
} Stack;

void stack_init(Stack *s)          { s->top = -1; }
bool stack_empty(const Stack *s)   { return s->top < 0; }
bool stack_full(const Stack *s)    { return s->top >= STACK_MAX - 1; }
int  stack_size(const Stack *s)    { return s->top + 1; }

bool stack_push(Stack *s, int val) {
    if (stack_full(s)) return false;
    s->data[++s->top] = val;
    return true;
}

bool stack_pop(Stack *s, int *out) {
    if (stack_empty(s)) return false;
    *out = s->data[s->top--];
    return true;
}

bool stack_peek(const Stack *s, int *out) {
    if (stack_empty(s)) return false;
    *out = s->data[s->top];
    return true;
}

/* Classic stack application: check balanced parentheses */
bool is_balanced(const char *expr) {
    Stack s;
    stack_init(&s);

    for (int i = 0; expr[i]; i++) {
        char c = expr[i];
        if (c == '(' || c == '[' || c == '{') {
            stack_push(&s, c);   /* push opening bracket */
        } else if (c == ')' || c == ']' || c == '}') {
            int top;
            if (!stack_pop(&s, &top)) return false;   /* no matching opener */
            if ((c == ')' && top != '(') ||
                (c == ']' && top != '[') ||
                (c == '}' && top != '{')) return false;
        }
    }
    return stack_empty(&s);   /* unmatched openers left over = unbalanced */
}

int main(void) {
    Stack s;
    stack_init(&s);

    for (int i = 1; i <= 5; i++) stack_push(&s, i * 10);

    int val;
    while (stack_pop(&s, &val)) printf("%d ", val);  /* 50 40 30 20 10 */
    printf("\n");

    printf("balanced: %s\n", is_balanced("{[()]}") ? "yes" : "no");
    printf("balanced: %s\n", is_balanced("{[(])}") ? "yes" : "no");
    return 0;
}

Queue (Ring Buffer)

A queue is a first-in, first-out (FIFO) data structure. Items are added at the back and removed from the front. Queues are used for task scheduling, breadth-first search, and producer-consumer systems. A ring buffer (circular array) implements a fixed-capacity queue with O(1) enqueue and dequeue without ever moving data.

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

#define QUEUE_CAP 8

typedef struct {
    int    data[QUEUE_CAP];
    int    head, tail, size;
} Queue;

void  queue_init(Queue *q)        { q->head = q->tail = q->size = 0; }
bool  queue_empty(const Queue *q) { return q->size == 0; }
bool  queue_full(const Queue *q)  { return q->size == QUEUE_CAP; }
int   queue_size(const Queue *q)  { return q->size; }

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

bool queue_dequeue(Queue *q, int *out) {
    if (queue_empty(q)) return false;
    *out = q->data[q->head];
    q->head = (q->head + 1) % QUEUE_CAP;  /* advance head, wrap around */
    q->size--;
    return true;
}

bool queue_peek(const Queue *q, int *out) {
    if (queue_empty(q)) return false;
    *out = q->data[q->head];
    return true;
}

int main(void) {
    Queue q;
    queue_init(&q);

    for (int i = 1; i <= 5; i++) queue_enqueue(&q, i * 10);

    int val;
    while (queue_dequeue(&q, &val)) printf("%d ", val);  /* 10 20 30 40 50 */
    printf("\n");
    return 0;
}

Hash Table (Separate Chaining)

A hash table maps keys to values in O(1) average time using a hash function to compute an array index. When two keys hash to the same index (a collision), separate chaining stores them as a linked list at that index. Good hash functions distribute keys uniformly to keep chains short.

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

#define HT_SIZE 64

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

typedef struct {
    KVNode *buckets[HT_SIZE];
    size_t  count;
} HashTable;

/* djb2 hash — fast, simple, good distribution for strings */
static unsigned int hash(const char *key) {
    unsigned int h = 5381;
    while (*key) h = ((h << 5) + h) + (unsigned char)*key++;
    return h % HT_SIZE;
}

void ht_init(HashTable *ht) {
    memset(ht->buckets, 0, sizeof(ht->buckets));
    ht->count = 0;
}

void ht_set(HashTable *ht, const char *key, int value) {
    unsigned int idx = hash(key);
    KVNode *node = ht->buckets[idx];

    /* If key already exists, update its value in place */
    while (node) {
        if (strcmp(node->key, key) == 0) {
            node->value = value;
            return;
        }
        node = node->next;
    }

    /* Key not found — insert new node at front of the chain */
    KVNode *n = malloc(sizeof(KVNode));
    n->key   = strdup(key);
    n->value = value;
    n->next  = ht->buckets[idx];
    ht->buckets[idx] = n;
    ht->count++;
}

bool ht_get(const HashTable *ht, const char *key, int *out) {
    unsigned int idx = hash(key);
    KVNode *node = ht->buckets[idx];
    while (node) {
        if (strcmp(node->key, key) == 0) {
            *out = node->value;
            return true;
        }
        node = node->next;
    }
    return false;
}

void ht_delete(HashTable *ht, const char *key) {
    unsigned int idx = hash(key);
    KVNode **pp = &ht->buckets[idx];   /* pointer-to-pointer simplifies removal */
    while (*pp) {
        if (strcmp((*pp)->key, key) == 0) {
            KVNode *dead = *pp;
            *pp = dead->next;
            free(dead->key);
            free(dead);
            ht->count--;
            return;
        }
        pp = &(*pp)->next;
    }
}

void ht_free(HashTable *ht) {
    for (int i = 0; i < HT_SIZE; i++) {
        KVNode *node = ht->buckets[i];
        while (node) {
            KVNode *next = node->next;
            free(node->key);
            free(node);
            node = next;
        }
        ht->buckets[i] = NULL;
    }
    ht->count = 0;
}

int main(void) {
    HashTable ht;
    ht_init(&ht);

    ht_set(&ht, "alice",   95);
    ht_set(&ht, "bob",     87);
    ht_set(&ht, "charlie", 92);
    ht_set(&ht, "alice",   98);   /* update existing key */

    int score;
    if (ht_get(&ht, "alice", &score))   printf("alice:   %d\n", score);
    if (ht_get(&ht, "bob",   &score))   printf("bob:     %d\n", score);
    if (!ht_get(&ht, "dave", &score))   printf("dave not found\n");

    ht_delete(&ht, "bob");
    printf("count after delete: %zu\n", ht.count);

    ht_free(&ht);
    return 0;
}

Binary Search Tree

A binary search tree (BST) stores values so that for every node, all values in its left subtree are smaller and all values in its right subtree are larger. This invariant enables O(log n) search, insertion, and deletion on a balanced tree. In-order traversal visits nodes in sorted order, which is why BSTs are useful for sorted data sets and range queries.

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

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

/* Insert a key — returns new root (may be unchanged if tree already has nodes) */
BST *bst_insert(BST *root, int key) {
    if (!root) {
        BST *n = malloc(sizeof(BST));
        n->key = key;
        n->left = n->right = 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);
    /* equal keys are ignored — no duplicates */
    return root;
}

/* Search iteratively — O(log n) for balanced trees */
BST *bst_find(BST *root, int key) {
    while (root) {
        if      (key < root->key) root = root->left;
        else if (key > root->key) root = root->right;
        else                      return root;
    }
    return NULL;
}

/* In-order traversal: visits nodes in ascending sorted order */
void bst_inorder(const BST *root) {
    if (!root) return;
    bst_inorder(root->left);
    printf("%d ", root->key);
    bst_inorder(root->right);
}

BST *bst_min(BST *root) {
    while (root && root->left) root = root->left;
    return root;
}

/* Delete a key — three cases: no children, one child, two children */
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 {
        /* Node found — handle the three cases */
        if (!root->left) {
            BST *right = root->right;
            free(root);
            return right;
        }
        if (!root->right) {
            BST *left = root->left;
            free(root);
            return left;
        }
        /* Two children: replace with in-order successor (smallest in right subtree) */
        BST *succ = bst_min(root->right);
        root->key   = succ->key;
        root->right = bst_delete(root->right, succ->key);
    }
    return root;
}

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

int main(void) {
    BST *tree = NULL;
    int keys[] = {5, 3, 7, 1, 4, 6, 8};
    for (int i = 0; i < 7; i++) tree = bst_insert(tree, keys[i]);

    printf("In-order: ");
    bst_inorder(tree);   /* 1 3 4 5 6 7 8 — sorted! */
    printf("\n");

    printf("Find 4: %s\n", bst_find(tree, 4) ? "found" : "not found");
    printf("Find 9: %s\n", bst_find(tree, 9) ? "found" : "not found");

    tree = bst_delete(tree, 3);
    printf("After deleting 3: ");
    bst_inorder(tree);   /* 1 4 5 6 7 8 */
    printf("\n");

    bst_free(tree);
    return 0;
}