Data structures in C · CMPUT-201 Lesson 9

Python gives you lists, dictionaries and sets ready-made. C gives you arrays, structs, pointers and malloc, and expects you to build the rest. Building data structures yourself is excellent practice in everything this course has covered so far, and it teaches how Python's own structures work underneath: CPython's list is a dynamic array and its dict is a hash table, both written in C. This lesson builds four classic structures, a singly linked list, a stack, a dynamic array and a hash table with separate chaining, each with careful ownership and complete cleanup, and then shows how function pointers let one sorting function, qsort, sort any kind of data. It ends with opaque types, the C technique for hiding a data structure's implementation behind a header. Analysing the efficiency of these structures properly is the job of CMPUT-204; here the focus is on implementing them correctly.

Linked lists

A singly linked list is a chain of nodes, each a struct holding a value and a pointer to the next node. The list itself is just a pointer to the first node, the head, and the last node's next pointer is NULL. Inserting at the front takes constant time regardless of the list's length, because only two pointers change; finding an element means walking from the head. Lists grow one node at a time with no copying, which suits data whose size changes unpredictably, but they use extra memory for the pointers and are slower to traverse than arrays because the nodes are scattered in memory.

A head pointer variable pointing to the first of three nodes. Each node is a box divided into two parts: a value (30, 20, 10) and a next pointer. Arrows run from each next pointer to the following node, and the last node's next pointer is NULL. Below, a new node with value 40 is shown being inserted at the front: its next pointer is set to the old first node and head is redirected to it. — A singly linked list, and inserting a node at the front

Inserting at the head must change the caller's head pointer, so the function takes a pointer to that pointer, a struct node **, as lesson 5 anticipated. Freeing a list must save each node's next pointer before freeing the node, because after free the node's memory may not be read.

A singly linked list with insertion, search, removal and cleanup

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

struct node {
    int value;
    struct node *next;
};

/* Insert at the front; returns false if memory runs out. */
static bool push_front(struct node **head, int value) {
    struct node *n = malloc(sizeof *n);
    if (n == NULL) return false;
    n->value = value;
    n->next = *head;          /* new node points to the old first node */
    *head = n;                /* the caller's head now points to the new node */
    return true;
}

static bool contains(const struct node *head, int value) {
    for (const struct node *p = head; p != NULL; p = p->next) {
        if (p->value == value) return true;
    }
    return false;
}

/* Remove the first node holding value; returns true if one was removed. */
static bool remove_value(struct node **head, int value) {
    for (struct node **link = head; *link != NULL; link = &(*link)->next) {
        if ((*link)->value == value) {
            struct node *dead = *link;
            *link = dead->next;   /* unlink */
            free(dead);
            return true;
        }
    }
    return false;
}

static void free_list(struct node *head) {
    while (head != NULL) {
        struct node *next = head->next;   /* save before freeing */
        free(head);
        head = next;
    }
}

static void print_list(const struct node *head) {
    for (const struct node *p = head; p; p = p->next) printf("%d -> ", p->value);
    printf("NULL\n");
}

int main(void) {
    struct node *list = NULL;
    for (int v = 10; v <= 40; v += 10) {
        if (!push_front(&list, v)) { free_list(list); return 1; }
    }
    print_list(list);
    printf("contains 20? %s\n", contains(list, 20) ? "yes" : "no");
    remove_value(&list, 20);
    remove_value(&list, 40);
    print_list(list);
    free_list(list);
    return 0;
}

Output

40 -> 30 -> 20 -> 10 -> NULL
contains 20? yes
30 -> 10 -> NULL

remove_value uses a well-known idiom: instead of tracking the previous node, it walks a pointer to the link that points at the current node, starting with the head pointer itself. Unlinking is then a single assignment, *link = dead->next, whether the node is first or in the middle, with no special case. Because the program is compiled with AddressSanitizer and ends without a report, we know it frees every node and never touches freed memory.

Stacks

A stack is a last-in, first-out collection: push adds an item on top and pop removes the most recently pushed item, like the call stack in lesson 4. It can be built on a linked list, pushing and popping at the head, or on an array with a count of items. The array version below has a fixed capacity, chosen by the caller, and reports overflow and underflow instead of crashing. Stacks are used for undo histories, expression evaluation and depth-first search; the example checks whether brackets in a string are balanced, a task every compiler performs.

An array-based stack used to check balanced brackets

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

#define STACK_CAP 64

struct stack {
    char items[STACK_CAP];
    size_t count;
};

static bool push(struct stack *s, char c) {
    if (s->count == STACK_CAP) return false;      /* overflow */
    s->items[s->count++] = c;
    return true;
}

static bool pop(struct stack *s, char *out) {
    if (s->count == 0) return false;              /* underflow */
    *out = s->items[--s->count];
    return true;
}

static bool balanced(const char *text) {
    struct stack s = {.count = 0};
    for (size_t i = 0; text[i]; i++) {
        char c = text[i], top;
        if (strchr("([{", c)) {
            if (!push(&s, c)) return false;
        } else if (strchr(")]}", c)) {
            if (!pop(&s, &top)) return false;
            if ((c == ')' && top != '(') || (c == ']' && top != '[') || (c == '}' && top != '{'))
                return false;
        }
    }
    return s.count == 0;
}

int main(void) {
    const char *tests[] = {"a[i] = f(x) + {y}", "if (a[0] > b) {", "(]", "((()))[]{}"};
    for (size_t i = 0; i < 4; i++) {
        printf("%-20s %s\n", tests[i], balanced(tests[i]) ? "balanced" : "not balanced");
    }
    return 0;
}

Output

a[i] = f(x) + {y}    balanced
if (a[0] > b) {      not balanced
(]                   not balanced
((()))[]{}           balanced

Dynamic arrays

A dynamic array, also called a vector, combines the fast indexing of an array with the ability to grow. It keeps a heap block with some spare capacity, a count of elements in use and the capacity. Appending stores into the next free slot; when the block is full, it is enlarged with realloc to twice its capacity, so the occasional expensive copy is spread over many cheap appends, as lesson 7's worked problem calculated. This is exactly how Python's list and C++'s std::vector work. The version below counts how many element copies the reallocations could have caused, to confirm the arithmetic.

A dynamic array that doubles its capacity when full

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

struct vec {
    int *data;
    size_t len, cap;
};

static bool vec_push(struct vec *v, int x, size_t *copies) {
    if (v->len == v->cap) {
        size_t new_cap = v->cap ? v->cap * 2 : 1;
        int *tmp = realloc(v->data, new_cap * sizeof *tmp);
        if (tmp == NULL) return false;
        *copies += v->len;               /* elements realloc may have moved */
        v->data = tmp;
        v->cap = new_cap;
    }
    v->data[v->len++] = x;
    return true;
}

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

int main(void) {
    struct vec v = {NULL, 0, 0};
    size_t copies = 0;
    for (int i = 0; i < 1000; i++) {
        if (!vec_push(&v, i * i, &copies)) { vec_free(&v); return 1; }
    }
    printf("len %zu, cap %zu, element copies %zu\n", v.len, v.cap, copies);
    printf("v[999] = %d\n", v.data[999]);
    vec_free(&v);
    return 0;
}

Output

len 1000, cap 1024, element copies 1023
v[999] = 998001

Hash tables

A hash table stores key-value pairs and finds a key in roughly constant time on average. It keeps an array of buckets. A hash function turns the key into a number, and the number modulo the array size chooses a bucket. Different keys can land in the same bucket, a collision, so each bucket holds a linked list of the entries that hashed there; this design is called separate chaining. Looking up a key hashes it, then searches only that bucket's short list. The average list length is the load factor, the number of entries divided by the number of buckets; keeping it near 1, by enlarging the table and rehashing as it fills, keeps lookups fast. Python's dict uses a different collision strategy, open addressing, but the same principles.

A vertical array of 8 buckets numbered 0 to 7. Keys are shown passing through a hash function box, which maps apple to bucket 2, kiwi to bucket 5 and grape also to bucket 5. Bucket 2 points to a node holding apple and its count; bucket 5 points to a chain of two nodes, kiwi then grape, showing a collision resolved by chaining. Other buckets are empty, shown as NULL. — A hash table with separate chaining: keys that collide share a bucket's list

The example counts word frequencies, the classic use of a dictionary, with the djb2 string hash function by Daniel J. Bernstein: start at 5381 and, for each character, multiply by 33 and add the character. Unsigned arithmetic makes the wrap-around well defined. Each entry owns a copy of its key, made with malloc, so the table's destroy function must free both the keys and the nodes.

Counting words with a chained hash table

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

#define NBUCKETS 8

struct entry {
    char *key;
    int count;
    struct entry *next;
};

static unsigned long hash(const char *s) {          /* djb2 */
    unsigned long h = 5381;
    for (; *s; s++) h = h * 33 + (unsigned char)*s;
    return h;
}

static int add_word(struct entry *table[], const char *word) {
    size_t b = hash(word) % NBUCKETS;
    for (struct entry *e = table[b]; e; e = e->next) {
        if (strcmp(e->key, word) == 0) { e->count++; return 0; }
    }
    struct entry *e = malloc(sizeof *e);
    char *copy = malloc(strlen(word) + 1);
    if (e == NULL || copy == NULL) { free(e); free(copy); return -1; }
    strcpy(copy, word);                              /* size checked above */
    e->key = copy;
    e->count = 1;
    e->next = table[b];                              /* insert at front of chain */
    table[b] = e;
    return 0;
}

static void destroy(struct entry *table[]) {
    for (size_t b = 0; b < NBUCKETS; b++) {
        struct entry *e = table[b];
        while (e) {
            struct entry *next = e->next;
            free(e->key);
            free(e);
            e = next;
        }
        table[b] = NULL;
    }
}

int main(void) {
    struct entry *table[NBUCKETS] = {NULL};
    const char *words[] = {"the", "cat", "sat", "on", "the", "mat", "the", "cat", "ran"};
    for (size_t i = 0; i < sizeof words / sizeof words[0]; i++) {
        if (add_word(table, words[i]) != 0) { destroy(table); return 1; }
    }
    for (size_t b = 0; b < NBUCKETS; b++) {
        printf("bucket %zu:", b);
        for (struct entry *e = table[b]; e; e = e->next) printf(" %s=%d", e->key, e->count);
        printf("\n");
    }
    destroy(table);
    return 0;
}

Output

bucket 0:
bucket 1:
bucket 2: on=1
bucket 3:
bucket 4:
bucket 5: sat=1 cat=2
bucket 6: ran=1 the=3
bucket 7: mat=1

With only eight buckets and six distinct words, some buckets hold two entries and some none; a real table would start larger and grow. Note how much code C needs for what Python does in one line with collections.Counter. That is the cost of control: you choose the hash function, the memory layout and the growth policy, which is why high-performance systems are still written this way.

Worked problem

Load factor and expected chain length

A chained hash table has 1,024 buckets and holds 3,000 entries, spread evenly by a good hash function. What is the load factor, how many key comparisons does a successful lookup need on average, and what would doubling the table to 2,048 buckets achieve?

Show solution

Load factor = entries / buckets = 3,000 / 1,024, about 2.93.
An unsuccessful search scans a whole chain, about 2.93 entries on average. A successful search finds its key about halfway along its chain, roughly 1 + 2.93 / 2, about 2.5 comparisons.
Doubling to 2,048 buckets gives a load factor of about 1.46, so a successful lookup needs about 1.7 comparisons and an unsuccessful one about 1.5.
Growing costs a one-time rehash of all 3,000 entries, since each key's bucket depends on the table size; doing it whenever the load factor passes a threshold keeps the average cost of operations constant.

Answer: Load factor about 2.93 (about 2.5 comparisons per successful lookup); doubling halves it to about 1.46.

Function pointers and qsort

A function's name, used without parentheses, is a pointer to the function, and it can be stored in a variable and called through it. The declaration syntax is awkward: int (*cmp)(const void *, const void *) declares cmp as a pointer to a function taking two const void * and returning int. Function pointers let you pass behaviour as an argument, the C equivalent of passing a function or lambda in Python, as in sorted(items, key=...). The standard library's qsort uses them to sort an array of any type: you give it the array, the number of elements, the size of each and a comparison function that returns a negative, zero or positive int to order two elements, received as const void * and converted to the real type inside.

qsort sorts any array, given a comparison function

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

struct runner {
    char name[16];
    int age;
    double minutes;           /* 10 km time */
};

static int by_time(const void *a, const void *b) {
    const struct runner *x = a, *y = b;
    return (x->minutes > y->minutes) - (x->minutes < y->minutes);   /* -1, 0 or 1 */
}

static int by_age_then_name(const void *a, const void *b) {
    const struct runner *x = a, *y = b;
    if (x->age != y->age) return (x->age > y->age) - (x->age < y->age);
    return strcmp(x->name, y->name);
}

static void show(const char *title, const struct runner r[], size_t n) {
    printf("%s:\n", title);
    for (size_t i = 0; i < n; i++) printf("  %-6s %2d %6.1f\n", r[i].name, r[i].age, r[i].minutes);
}

int main(void) {
    struct runner r[] = {
        {"Mei", 34, 47.2}, {"Omar", 29, 41.8}, {"Ana", 34, 52.5}, {"Luc", 29, 44.0},
    };
    size_t n = sizeof r / sizeof r[0];
    int (*cmp)(const void *, const void *) = by_time;    /* a function pointer */
    qsort(r, n, sizeof r[0], cmp);
    show("fastest first", r, n);
    qsort(r, n, sizeof r[0], by_age_then_name);
    show("by age, then name", r, n);
    return 0;
}

Output

fastest first:
  Omar   29   41.8
  Luc    29   44.0
  Mei    34   47.2
  Ana    34   52.5
by age, then name:
  Luc    29   44.0
  Omar   29   41.8
  Ana    34   52.5
  Mei    34   47.2

The comparison (x > y) - (x < y) yields -1, 0 or 1 without the overflow risk of the tempting return x - y, which is undefined behaviour when the subtraction overflows and does not work for doubles at all. qsort is not guaranteed to be stable, meaning equal elements may change order, so break ties explicitly, as by_age_then_name does with the name. Function pointers are also how C programs implement callbacks, plug-in tables and the dispatch tables at the heart of interpreters and device drivers.

Opaque types and abstract data types

An abstract data type defines operations without exposing representation. In C, the header declares an incomplete struct type, struct counter;, and functions that take pointers to it; the full struct definition lives only in the .c file. Users can hold and pass struct counter * pointers but cannot see or touch the members, so the implementation can change without breaking them, and the module controls creation and destruction. This is the C equivalent of private fields, and the standard library uses it for FILE.

An opaque type: users see only a pointer and the operations

/* counter.h - a word counter whose representation is hidden */
#ifndef COUNTER_H
#define COUNTER_H

typedef struct counter Counter;          /* incomplete type: members hidden */

Counter *counter_new(void);              /* returns NULL if out of memory; free with counter_free */
int counter_add(Counter *c, const char *word);     /* 0 on success, -1 if out of memory */
int counter_get(const Counter *c, const char *word);
void counter_free(Counter *c);           /* accepts NULL */

#endif

Common mistakes

MistakeFreeing a list node and then reading its next pointer.
InsteadSave next in a local variable before calling free.
MistakeWriting a push_front that takes struct node *head and assigns head = n.
InsteadTake struct node **head so the caller's pointer changes.
MistakeReturning a - b from a qsort comparison function.
InsteadUse (a > b) - (a < b) to avoid overflow and to handle doubles.
MistakeStoring a pointer to the caller's string as a hash table key.
InsteadCopy the key, so the table owns it and the caller can reuse its buffer.
MistakeLetting a hash table's load factor grow without limit.
InsteadEnlarge the table and rehash when the load factor passes a threshold.
MistakeForgetting to free the keys as well as the nodes in destroy.
InsteadFree everything each node owns, then the node itself.

Summary and key terms

A singly linked list chains nodes with next pointers; insertion at the head is constant time and searching walks the list.
Functions that change the head pointer take a pointer to it, and freeing must save next before free.
A stack is last-in, first-out and can be built on an array with overflow and underflow checks.
A dynamic array grows by doubling with realloc, giving amortized constant-time appends.
A hash table maps keys to buckets with a hash function; chaining handles collisions and the load factor governs speed.
Function pointers pass behaviour as data; qsort sorts any array with a comparison function.
Opaque types hide a structure's members behind a header of operations.

Linked list: A sequence of nodes in which each node points to the next.
Node: A struct in a linked structure holding data and one or more pointers.
Stack: A last-in, first-out collection with push and pop operations.
Dynamic array: An array on the heap that grows by reallocating to a larger capacity.
Hash function: A function that maps a key to an integer used to choose a bucket.
Collision: Two different keys mapping to the same bucket.
Separate chaining: Resolving collisions by keeping a linked list in each bucket.
Load factor: The number of entries in a hash table divided by the number of buckets.
Function pointer: A pointer that holds the address of a function and can be called.
Opaque type: A struct declared but not defined in a header, so users cannot see its members.

Practice problems

Work each problem on paper first, then reveal the answer to check.

Write the struct for a doubly linked list node holding a double.
Show answer
struct dnode { double value; struct dnode *prev, *next; };
Write a function that returns the length of a singly linked list.
Show answer
size_t length(const struct node *p) { size_t n = 0; for (; p; p = p->next) n++; return n; }
Why does push_front take struct node ** rather than struct node *?
Show answer
It must change the caller's head pointer, so it needs that pointer's address.
What happens if you pop from an empty array stack without a check?
Show answer
count wraps or goes below zero and the code reads outside the array: undefined behaviour.
A dynamic array starts at capacity 4 and doubles. What is its capacity after 100 appends?
Show answer
128 (4, 8, 16, 32, 64, 128).
Compute djb2 for the one-character string "a" (character code 97).
Show answer
5381 x 33 + 97 = 177,670.
What is the load factor of a table with 50 entries in 200 buckets?
Show answer
0.25.
Write a qsort comparison function for an array of int.
Show answer
int cmp(const void *a, const void *b) { int x = *(const int *)a, y = *(const int *)b; return (x > y) - (x < y); }
Declare a variable op that can point to a function taking two doubles and returning a double.
Show answer
double (*op)(double, double);
Why use an opaque type for a library's main data structure?
Show answer
Users cannot depend on its members, so the implementation can change, and the library controls creation and cleanup.