Data Structures in C — C Programming Course

What you'll learn

Data structures organize values around the operations a program needs. In C, implementing them also means defining representation invariants, allocation ownership, failure behavior, and cleanup.

By the end, you'll be able to:

Design an abstract data type behind an opaque interface
Implement and clean up linked nodes
Choose among arrays, lists, stacks, queues, tables, and trees
Build generic ownership-aware containers with void *

Choose structure by operations and constraints

Array

index

▣ ▣ ▣ ▣

O(1) indexed access

Linked list

links

□ → □ → □

O(1) front insertion

Hash table

hash

▤ → buckets

O(1) expected lookup

Search tree

order

△ branching

O(log n) when balanced

Abstract data types

An abstract data type defines observable operations and guarantees while hiding its representation. An incomplete structure declaration lets clients hold pointers without accessing private members.

int_stack.h

// int_stack.h
#ifndef INT_STACK_H
#define INT_STACK_H

#include <stdbool.h>
#include <stddef.h>

typedef struct IntStack IntStack; // incomplete, opaque type

IntStack *int_stack_create(void);
void int_stack_destroy(IntStack *stack);
bool int_stack_push(IntStack *stack, int value);
bool int_stack_pop(IntStack *stack, int *value);
size_t int_stack_size(const IntStack *stack);

#endif

Key idea

Encapsulation in C is a module property: public declarations live in the header, while the complete structure and helper functions stay in the implementation file.

Linked lists

A linked list stores each value in a separately allocated node containing a link to the next node. Front insertion and removal are constant-time; indexed access requires traversal.

linked_list.c

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

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

bool push_front(Node **head, int value) {
    Node *node = malloc(sizeof *node);
    if (node == NULL) return false;

    node->value = value;
    node->next = *head;
    *head = node;
    return true;
}

bool pop_front(Node **head, int *value) {
    if (head == NULL || *head == NULL) return false;

    Node *removed = *head;
    *value = removed->value;
    *head = removed->next;
    free(removed);
    return true;
}

void destroy_list(Node **head) {
    Node *current = *head;
    while (current != NULL) {
        Node *next = current->next;
        free(current);
        current = next;
    }
    *head = NULL;
}

int main(void) {
    Node *head = NULL;
    push_front(&head, 10);
    push_front(&head, 20);

    int value;
    while (pop_front(&head, &value)) printf("%d ", value);
    putchar('\n');
    destroy_list(&head);
    return 0;
}

Watch out

Save current->next before freeing current. Reading the next link afterward would be use-after-free.

Stacks & queues

Structure	Policy	Core operations	Typical uses
Stack	LIFO	push / pop / top	Parsing, undo, depth-first traversal
Queue	FIFO	enqueue / dequeue / front	Scheduling, breadth-first traversal

A list head naturally implements a stack. A linked queue tracks both front and back so enqueue and dequeue remain constant-time.

queue_model.c

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

typedef struct {
    Node *front;
    Node *back;
    size_t size;
} Queue;

/* Invariant:
 * size == 0  => front == NULL && back == NULL
 * size > 0   => front != NULL && back != NULL && back->next == NULL
 */

Tip

Write invariants beside the representation before implementing operations. Check that every successful and failed operation preserves them.

Hash tables

A hash function maps a key to a number; modulo chooses a bucket. Different keys can collide, so a table needs chaining or open addressing plus equality checks.

hash.c

#include <stddef.h>
#include <stdint.h>

uint64_t hash_string(const char *text) {
    uint64_t hash = UINT64_C(14695981039346656037);
    while (*text != '\0') {
        hash ^= (unsigned char) *text++;
        hash *= UINT64_C(1099511628211);
    }
    return hash;
}

size_t bucket_for(const char *key, size_t bucket_count) {
    return (size_t) (hash_string(key) % bucket_count);
}

Keep the bucket count nonzero
Compare full keys after hashes lead to a bucket
Resize when the load factor becomes too high
Preserve keys or clearly transfer their ownership

Note

Expected constant-time lookup depends on a suitable hash function and controlled load. Adversarial collisions can degrade performance.

Binary search trees

Each search-tree node partitions values: smaller keys go left and larger keys go right. Search follows one path; cleanup must visit children before freeing their parent.

search_tree.c

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

typedef struct TreeNode {
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

bool contains(const TreeNode *root, int target) {
    while (root != NULL) {
        if (target == root->value) return true;
        root = target < root->value ? root->left : root->right;
    }
    return false;
}

void destroy_tree(TreeNode *root) {
    if (root == NULL) return;
    destroy_tree(root->left);
    destroy_tree(root->right);
    free(root);
}

Watch out

A plain binary search tree can become a linked list when insertion order is already sorted. Balanced trees maintain logarithmic height with additional rules.

Generic containers

A void * can point to any object type. Generic containers store such pointers but lose compile-time knowledge of the real type, so their API contract must restore it.

generic_list.c

#include <stddef.h>
#include <stdlib.h>

typedef void (*DestroyValue)(void *value);

typedef struct GenericNode {
    void *value;
    struct GenericNode *next;
} GenericNode;

void generic_list_destroy(GenericNode *head, DestroyValue destroy_value) {
    while (head != NULL) {
        GenericNode *next = head->next;
        if (destroy_value != NULL) destroy_value(head->value);
        free(head);
        head = next;
    }
}

Key idea

A destructor callback distinguishes owning containers from borrowing containers. If the container owns elements, destruction must release both each element and every node.

Ownership & invariants

Define who owns nodes, keys, and stored values
Leave the structure unchanged when an allocation fails
Update links in an order that never loses reachable nodes
Keep size counters synchronized with successful operations
Provide one destroy operation safe for empty and partially built states

Tip

Test the empty structure, one element, many elements, duplicate keys, missing values, allocation failure, and repeated create/destroy cycles under a memory sanitizer.

Recap & quick check

Key takeaways

An ADT exposes operations and invariants while hiding its representation.
Linked-list insertion is cheap, but traversal and allocation add costs.
Stacks are LIFO; queues are FIFO and typically track both ends.
Hash-table speed depends on distribution, collision handling, and load factor.
Generic containers need explicit type and ownership contracts.

Quick check

1. What does an opaque structure in a header hide?

2. Which policy defines a queue?

3. Why compare keys after selecting a hash bucket?

4. Why destroy tree children before their parent?

You can now build ownership-aware containers. Next up: Module 17 — Algorithms & Complexity, where we measure and improve the work those structures perform.