Data Structures

Choosing a Structure

Each structure trades speed in some operations against others. The operational note that matters: contiguous memory (arrays) wins on cache locality; linked nodes win on cheap insertion anywhere; hash tables win on lookup; trees win on order.

Dynamic Array (Vector)

The vector wraps a heap array with capacity and length, and doubles capacity when full — amortized O(1) appends with excellent locality. It is the backbone of C programs that read unknown amounts of data.

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

typedef struct {
    int *data;      // heap array of capacity elements
    size_t len;     // current number of elements
    size_t cap;     // allocated capacity
} Vector;

// append: grow by doubling when full; abort-like NULL check for brevity
void vec_push(Vector *v, int value) {
    if (v->len == v->cap) {
        v->cap = v->cap ? v->cap * 2 : 4;        // 0 -> 4, then double
        int *grown = realloc(v->data, v->cap * sizeof(int));
        if (grown == NULL) { exit(1); }         // keep the example honest
        v->data = grown;
    }
    v->data[v->len++] = value;                  // place then advance
}

void vec_free(Vector *v) { free(v->data); v->data = NULL; v->len = v->cap = 0; }

int main(void) {
    Vector v = {0};
    for (int i = 0; i < 5; i++) vec_push(&v, i * i);
    for (size_t i = 0; i < v.len; i++) printf("%d ", v.data[i]);  // 0 1 4 9 16
    printf("\n");
    vec_free(&v);
    return 0;
}

Singly Linked List

The list stores nodes anywhere in memory, each holding a value and a pointer to the next node; the list itself is just a head pointer. Insertion at the head is O(1) — the classic advantage over arrays — while finding an element by value is O(n), and there is no cache-friendly locality.

Figure 1 — the head pointer anchors the chain; next == NULL marks the tail.

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

typedef struct Node Node;         // forward declaration for the self-reference
struct Node {
    int  value;                   // the payload
    Node *next;                   // pointer to the next node or NULL
};

// push a new node in front of the head — O(1)
Node *list_push(Node *head, int value) {
    Node *node = malloc(sizeof(Node));   // each node is a separate allocation
    if (node == NULL) return head;
    node->value = value;
    node->next  = head;                  // new head points to the old head
    return node;                         // the new head travels back to caller
}

void list_print(const Node *head) {
    for (const Node *cur = head; cur != NULL; cur = cur->next) {
        printf("%d -> ", cur->value);
    }
    printf("NULL\n");
}

void list_free(Node *head) {            // walk and free every node — no leaks
    while (head != NULL) {
        Node *next = head->next;        // save next BEFORE freeing this node
        free(head);
        head = next;
    }
}

int main(void) {
    Node *head = NULL;
    head = list_push(head, 3);
    head = list_push(head, 2);
    head = list_push(head, 1);
    list_print(head);                    // 1 -> 2 -> 3 -> NULL
    list_free(head);
    return 0;
}

Note the two must-remember details: list_free saves next before freeing, and single-linked deletion needs the previous node — which is why doubly-linked lists exist.

Stack & Queue

A stack is LIFO (last in, first out) — think undo history. A queue is FIFO (first in, first out) — think task dispatch. Both are just a vector or list wearing a restricted interface. A vector-backed stack is two operations:

#include <stdio.h>

// vector-backed stack: reuse the Vector type from above conceptually
// push:  v.data[v.len++] = value;
// pop:   return v.data[--v.len];   (LIFO: last pushed, first popped)

// array-backed queue with a ring: front advances modulo capacity
int main(void) {
    int q[8];                 // circular buffer of capacity 8
    int head = 0, tail = 0;   // empty when head == tail
    // enqueue: q[tail] = 5; tail = (tail + 1) % 8;
    // dequeue: int v = q[head]; head = (head + 1) % 8;
    // a ring buffer never copies data — it just moves indices around
    (void)q; (void)head; (void)tail;   // sizes shown for the pattern only
    return 0;
}

The ring-buffer trick — indices advance modulo capacity — is how sockets, audio, and kernel queues move data with zero copying.

Hash Table

A hash table maps keys to values in average O(1): a hash function turns the key into a bucket index, and collisions (two keys, one bucket) are resolved by chaining — each bucket holds a small linked list. This is the workhorse of caches, symbol tables, and word counters; the study projects page builds a full one.

Figure 2 — keys hash to buckets; collisions chain in small lists. Load factor keeps chains short.

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

#define BUCKETS 8

typedef struct Entry Entry;
struct Entry {          // one key/value pair in a bucket chain
    const char *key;
    int         value;
    Entry      *next;
};

// djb2: the classic string hash — good avalanche, tiny and fast
unsigned long hash_str(const char *s) {
    unsigned long h = 5381;
    while (*s) h = h * 33 + (unsigned char)*s++;
    return h;
}

// lookup: hash to a bucket, walk its chain comparing strings
int *table_get(Entry *table[], const char *key) {
    unsigned long h = hash_str(key) % BUCKETS;
    for (Entry *e = table[h]; e != NULL; e = e->next) {
        if (strcmp(e->key, key) == 0) return &e->value;   // found
    }
    return NULL;                     // absent
}

void table_put(Entry *table[], const char *key, int value) {
    int *slot = table_get(table, key);
    if (slot != NULL) { *slot = value; return; }   // update existing key
    Entry *e = malloc(sizeof(Entry));              // else chain a new entry
    e->key = key; e->value = value; e->next = table[hash_str(key) % BUCKETS];
    table[hash_str(key) % BUCKETS] = e;            // push onto the bucket
}

int main(void) {
    Entry *table[BUCKETS] = {0};                   // all buckets start empty
    table_put(table, "ada", 1);
    table_put(table, "bob", 2);
    printf("ada -> %d\n", *table_get(table, "ada"));   // 1
    printf("bob -> %d\n", *table_get(table, "bob"));   // 2
    return 0;
}

The load factor — entries divided by buckets — decides real performance. When it grows past ~0.75, resize and rehash every entry; that rehash is the one expensive step, amortized O(1) over time.

Binary Search Tree

A BST keeps values ordered: left subtree smaller, right subtree larger. Lookup, insert, and delete cost O(log n) on a balanced tree, and an in-order walk returns the values sorted. Without balancing (AVL/red-black), worst-case input degenerates the tree into a linked list — O(n) — which is why real libraries balance.

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

typedef struct TNode TNode;
struct TNode {
    int    value;
    TNode *left, *right;      // children; NULL when absent
};

// insert keeps the ordering invariant — recursive descent to the gap
TNode *tree_insert(TNode *root, int value) {
    if (root == NULL) {                       // found the insertion point
        TNode *n = malloc(sizeof(TNode));
        if (n) { n->value = value; n->left = n->right = NULL; }
        return n;
    }
    if (value < root->value)
        root->left  = tree_insert(root->left, value);
    else if (value > root->value)
        root->right = tree_insert(root->right, value);
    return root;                              // equal values: ignore duplicates
}

int tree_search(const TNode *root, int value) {
    if (root == NULL)          return 0;
    if (value == root->value)  return 1;
    return value < root->value ? tree_search(root->left, value)
                              : tree_search(root->right, value);
}

// in-order traversal emits the values sorted ascending
void tree_walk(const TNode *root) {
    if (root == NULL) return;
    tree_walk(root->left);
    printf("%d ", root->value);
    tree_walk(root->right);
}

int main(void) {
    TNode *root = NULL;
    int vals[] = {50, 30, 70, 20, 40, 60, 80};
    for (size_t i = 0; i < sizeof(vals) / sizeof(vals[0]); i++)
        root = tree_insert(root, vals[i]);
    printf("in-order: "); tree_walk(root);      // 20 30 40 50 60 70 80
    printf("\nfound 40? %s\n", tree_search(root, 40) ? "yes" : "no");
    return 0;
}

Next: algorithms — putting these structures to work sorting and searching.