C / Advanced: Language Boundaries and Systems / Lesson 15

Data Structures and Invariants

Derive operations from representation invariants and keep topology, ownership, and complexity visible in the design.

About 5 min readContent reviewed 2026-10-23

On this page

Lesson goals

State stack and linked-list invariants.
Handle empty, full, and allocation-failure cases.
Compare locality and asymptotic operation costs.

The invariant is the structure’s definition

A data structure is more than a collection of fields. Its representation invariant defines which field combinations are valid. For a bounded stack, zero <= length <= capacity and elements below length are initialized. A push must check capacity before writing; a pop must check nonemptiness before decrementing or reading.

Specify ownership and invalidation alongside topology. Does removing an element transfer its resources or destroy them? May callers keep pointers to elements after growth or removal? These answers determine whether an otherwise correct algorithm can be safely used. Keep failure behavior explicit: an unsuccessful push should generally preserve the previous valid stack.

A small stack with an atomic state update

The stack example checks all preconditions before changing length or writing an output value. The term atomic here means logically indivisible at the API level in this single-threaded example; it is not a C11 inter-thread atomic operation. Keeping those meanings separate prevents accidental concurrency claims.

After pushing three then eight, the first pop returns eight because the stack is last-in, first-out. Unused storage is not read. The fixed capacity avoids allocation and makes full behavior predictable, but an interface accepting externally chosen capacity would still need storage and arithmetic validation.

c A bounded last-in, first-out structure

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

struct stack { int data[4]; size_t length; };

static bool push(struct stack *s, int value)
{
    if (s->length == 4) return false;
    s->data[s->length++] = value;
    return true;
}

static bool pop(struct stack *s, int *out)
{
    if (s->length == 0) return false;
    *out = s->data[--s->length];
    return true;
}

int main(void)
{
    struct stack s = {.length = 0};
    int value = 0;
    if (!push(&s, 3) || !push(&s, 8) || !pop(&s, &value)) return 1;
    printf("popped=%d left=%zu\n", value, s.length);
    return 0;
}

Expected output

popped=8 left=1

main maintains a valid stack and live output object; popping returns the most recent value.

Links and owners are different roles

A singly linked list stores a next pointer in each node. A simple owning list requires an acyclic chain ending in null, with every node reachable exactly once and owned by the list. Inserting at the head takes constant pointer work once allocation succeeds. Finding an arbitrary position requires traversal.

The complete example allocates before publishing the new head, so failure leaves the previous chain intact. Destruction saves next before freeing the current node; reading current->next afterward would access an object whose lifetime has ended. The caller must not keep borrowed node pointers after destruction.

c An owning two-node chain

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

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

static bool prepend(struct node **head, int value)
{
    struct node *item = malloc(sizeof *item);
    if (item == NULL) return false;
    item->value = value; item->next = *head;
    *head = item;
    return true;
}

static void clear(struct node **head)
{
    while (*head != NULL) {
        struct node *next = (*head)->next;
        free(*head);
        *head = next;
    }
}

int main(void)
{
    struct node *head = NULL;
    if (!prepend(&head, 3) || !prepend(&head, 8)) { clear(&head); return 1; }
    printf("head=%d next=%d\n", head->value, head->next->value);
    clear(&head);
    return 0;
}

Expected output

head=8 next=3

On successful allocation, prepending reverses insertion order and clear releases each node once.

Count work and consider memory access

Asymptotic complexity describes growth of work as input size increases, not a universal elapsed time. Indexed access in a contiguous array is constant-time under the usual model; searching an unsorted array or list is linear. A balanced search tree can provide logarithmic search, but its balancing invariant must actually be maintained.

A linked list’s cheap insertion does not make it automatically faster than a vector. Node allocation, pointer chasing, cache behavior, and the cost of finding the insertion point matter. Choose a representation from measured workloads and required operations, rather than selecting the structure with the most appealing isolated complexity label.

Test transitions, not only stored values

Exercise empty-to-nonempty, nonempty-to-empty, full rejection, and partial-construction failure. For a dynamic array, test growth with borrowed pointers invalidated; for a list, test first, middle, and last removal under the selected ownership policy. An invariant checker in a debug build can expose corruption close to its source.

Do not run an unbounded traversal on a possibly cyclic corrupted list as a diagnosis shortcut. Use a bounded inspection or an appropriate cycle-checking strategy in a controlled test. Destruction assumes the structure’s ownership invariant; corruption may require diagnosing the earlier incorrect mutation rather than attempting speculative frees.

Common errors and fixes

Popping an empty stack reads outside its logical sequence.

Why it happens: The length was decremented before the empty check.
How to fix it: Reject empty input before changing state.
Prevent it next time: Test empty pop and verify output remains unchanged.

List destruction reads freed storage.

Why it happens: The next link was fetched after free.
How to fix it: Save next while the node is alive, then release it.
Prevent it next time: Review lifetime at each step of removal loops.

An allocation failure loses the old head.

Why it happens: The structure was mutated before the new node existed.
How to fix it: Allocate and initialize privately before publishing the link.
Prevent it next time: Require unchanged-on-failure for insertion.

Check your understanding

1. State what clear must guarantee for an already empty list and after clearing two nodes.

Show worked solution

For an empty list, the loop executes zero times and the head remains null. For two nodes, it saves the second pointer, frees the first, advances the owner, then repeats and ends with null. Every originally owned node is freed once and no node link is read after its lifetime ends. Borrowed pointers to either node are invalid afterward.

2. A workload repeatedly scans all values and rarely inserts. Explain why a contiguous vector may outperform a linked list despite occasional growth.