19. Data structures and algorithms

Choose how to store data and work on it

A data structure is a way to organize values; an algorithm is a sequence of steps that operates on them. The right choice depends on what the program needs to do, not only on how the data looks.

1. Describe the operations your program needs, such as insert, find, remove, or visit every item.
2. Choose a representation that makes those operations understandable and manageable.
3. Trace a small example by hand, then estimate how the work grows as the number of items grows.

For instance, searching an unsorted array may require checking each item, while a different representation can make some lookups faster at the cost of more setup or memory. This chapter compares those trade-offs step by step.

Once pointers, structures, and dynamic memory make sense, learn how to build
and analyze data structures:

• Dynamic arrays and resizable buffers.
• Singly and doubly linked lists.
• Stacks and queues.
• Hash tables.
• Trees, binary search trees, and heaps.
• Graph representations and traversals.

Learn algorithms such as linear and binary search, insertion sort, merge sort,
tree traversal, and breadth-first/depth-first search. Understand preconditions:
binary search, for example, requires sorted input.

Analyze time and space complexity using Big-O notation. Typical examples:

• Array access: O(1).
• Linear search: O(n).
• Binary search on sorted data: O(log n).
• A simple nested-loop comparison sort: commonly O(n^2).

Implement structures with clear invariants, test empty and one-element cases,
and document ownership and failure behavior.

Choose the representation before coding

For each structure, define its invariant: the rule that must remain true
after every operation. A stack might promise that only the last inserted
element can be removed. A queue might promise that the oldest remaining
element is removed first. A dynamic array might promise that its length never
exceeds its capacity and that all elements before its length are initialized.
Operations are correct only if they preserve these rules on both success and
failure.

Measure complexity as the input size grows. O(1) means a bounded amount of
work independent of input length; O(n) grows proportionally to the number
of elements; O(n^2) often comes from comparing each element with many
others. Big-O ignores constants and smaller terms, so it is a growth model,
not a stopwatch. Memory usage matters too: an algorithm can trade extra
storage for fewer operations.

Binary search is a good example of an algorithm with a precondition. It
repeatedly halves the search interval, but it is correct only when the data
is ordered according to the same comparison being used. If the array is not
sorted, first sort it or choose a different search algorithm.

#include <stddef.h>

 // A stack invariant: 0 <= size <= capacity. 
struct IntStack {
    int data[16];
    size_t size;
};

int stack_push(struct IntStack *stack, int value)
{
    if (stack->size == sizeof stack->data / sizeof stack->data[0]) {
        return 0;
    }
    stack->data[stack->size++] = value;
    return 1;
}

This fixed-capacity stack rejects a push when full. A complete API should
also validate the stack pointer and define pop behavior when empty.

Checkpoint: State an invariant for a stack and explain why binary search
cannot reliably find a value in an unsorted array.

Linked lists

A singly linked list stores a value and a pointer to the next node. The list
object usually stores a pointer to its first node. The final node points to
NULL. An empty list has a null head.

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

To insert at the front, allocate a node, initialize its value, set its next
to the old head, then update the head. If allocation fails, leave the list
unchanged. To remove the front, save the old head, update the head to the next
node, then free the removed node. Never read a node after freeing it.

List traversal follows links until NULL, so finding the nth element takes
linear time. Insertion at the front is constant time when the head is
available. A list has extra per-node pointer storage and often worse cache
locality than an array. Choose it when its insertion/removal characteristics
fit the workload, not just because it is a classic pointer exercise.

Each node needs one clear owner. A list destroy operation should walk the
nodes, save the next pointer before freeing the current node, and finally
reset the head. A shallow copy of the head pointer does not copy the nodes;
it creates two apparent owners and can cause double-free or dangling links.

Stacks and queues

A stack follows last-in, first-out order. Its core operations are push,
pop, and optionally peek. A queue follows first-in, first-out order and
has enqueue and dequeue. Define what happens when the structure is empty:
return a status and write an output value, rather than inventing a sentinel
that might also be a valid element.

A stack can use a dynamic array or linked list. A queue can use a linked
list, or a circular buffer. In a circular buffer, indices wrap to zero when
they reach the capacity; track both the number of elements and the next
insertion/removal positions so empty and full states are distinguishable.
Test wraparound, empty, full, and growth behavior.

#include <stddef.h>

#define QUEUE_CAPACITY 8

struct IntQueue {
    int data[QUEUE_CAPACITY];
    size_t head;
    size_t length;
};

int enqueue(struct IntQueue *queue, int value)
{
    if (queue->length == QUEUE_CAPACITY) {
        return 0;
    }
    size_t tail = (queue->head + queue->length) % QUEUE_CAPACITY;
    queue->data[tail] = value;
    ++queue->length;
    return 1;
}

int dequeue(struct IntQueue *queue, int *value)
{
    if (queue->length == 0 || value == NULL) {
        return 0;
    }
    *value = queue->data[queue->head];
    queue->head = (queue->head + 1) % QUEUE_CAPACITY;
    --queue->length;
    return 1;
}

The queue uses a count to distinguish empty from full. Include <stddef.h>
for size_t; production operations should also validate queue.

Hash tables

A hash table maps keys to buckets using a hash function. Different keys can
produce the same bucket (a collision), so the table needs a collision
strategy such as separate chaining or open addressing. The equality rule
must agree with the hash rule: keys considered equal must hash identically.

Average lookup can be close to constant time when hashes distribute keys
well and the load factor is controlled; worst-case lookup can be linear.
Resizing requires reinserting or re-indexing existing entries because bucket
positions depend on table capacity. Specify ownership for keys and values,
especially when they are pointers, and test collisions and resizing rather
than only the easy case.

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

size_t hash_bytes(const unsigned char *key, size_t length)
{
    size_t hash = (size_t)1469598103934665603ULL;
    for (size_t i = 0; i < length; ++i) {
        hash ^= key[i];
        hash *= (size_t)1099511628211ULL;
    }
    return hash;
}

size_t bucket_for(const unsigned char *key, size_t length, size_t capacity)
{
    return capacity == 0 ? 0 : hash_bytes(key, length) % capacity;
}

This is an illustrative byte hash, not a cryptographic hash and not
necessarily a suitable choice for hostile keys. A real table must resolve
collisions, define key equality and ownership, and avoid modulo by zero.

Trees and graphs

A binary search tree organizes values so keys in the left subtree compare
less than the node and keys in the right subtree compare greater, according
to a chosen duplicate policy. Search and insert take time proportional to
tree height; an unbalanced tree can degrade to a chain. Balanced trees
maintain additional rules to bound height.

A graph consists of vertices and edges. An adjacency list stores each
vertex's neighbors and is often space-efficient for sparse graphs. An
adjacency matrix stores whether each pair has an edge and can make edge
checks constant time, at the cost of quadratic storage. Breadth-first search
uses a queue; depth-first search uses recursion or an explicit stack. Track
visited vertices to avoid repeatedly traversing cycles.

#include <stddef.h>

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

int contains(const struct TreeNode *node, int target)
{
    while (node != NULL) {
        if (target == node->value) {
            return 1;
        }
        node = target < node->value ? node->left : node->right;
    }
    return 0;
}

This search assumes the tree obeys the binary-search-tree ordering rule and
does not address duplicate values. A graph traversal uses the same idea of
following references, but must also record visited vertices to handle cycles.

Choosing and verifying a data structure

For each candidate, compare:

• Required operations and their typical and worst-case costs.
• Memory overhead and allocation patterns.
• Whether elements need stable addresses or ordering.
• Ownership of elements and behavior on allocation failure.
• The invariant that every operation must preserve.

Implement a simple version first, write tests for empty and boundary states,
and compare it with a standard or well-tested implementation when one is
available.

enum CollectionKind {
    COLLECTION_ARRAY,  // Fast indexed access; insertion may shift elements. 
    COLLECTION_LIST    // Fast front insertion; indexed access is linear. 
};

enum CollectionKind choose_for_indexed_reads(void)
{
    return COLLECTION_ARRAY;
}

The code records a design decision; actual selection should follow measured
requirements such as access patterns, memory cost, and stable-address needs.

---