Dynamic Arrays and Stacks

This chapter implements a dynamic array (growable array) and a stack, the most fundamental dynamic structures in C.

Why This Matters

A dynamic array gives you array-like random access with automatic growth — the workhorse of most programs. A stack is a minimal, disciplined view of it, underpinning recursion, parsing, and undo systems.

Prerequisites

• c.ds.1 — foundations and complexity.
• c.memory.2 — malloc/realloc.

Core Concept

Dynamic array

A dynamic array holds a data pointer, a size (element count), and a capacity (allocated count). When size == capacity, it grows (typically doubling capacity). Amortized push is O(1).

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} Vec;

Stack

A stack is a last-in-first-out structure with push and pop. It can be implemented on top of a dynamic array, or with a fixed-size array for embedded use.

Examples

Dynamic array push

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

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
} Vec;

int vec_push(Vec *v, int value)
{
    if (v->size == v->capacity) {
        size_t new_cap = v->capacity ? v->capacity * 2 : 8;
        int *p = realloc(v->data, new_cap * sizeof *p);
        if (p == NULL) return -1;
        v->data = p;
        v->capacity = new_cap;
    }
    v->data[v->size++] = value;
    return 0;
}

void vec_free(Vec *v)
{
    free(v->data);
    v->data = NULL;
    v->size = v->capacity = 0;
}

Stack on a dynamic array

typedef struct {
    int *data;
    size_t top;
    size_t capacity;
} Stack;

int stack_push(Stack *s, int v) { /* grow if needed */ }
int stack_pop(Stack *s, int *out) {
    if (s->top == 0) return -1;
    *out = s->data[--s->top];
    return 0;
}

How It Works

Growth by doubling keeps the amortized cost of push O(1): occasional O(n) reallocations are paid off by many O(1) pushes. The stack is just the array with operations restricted to one end.

Variations

Growth factor

Doubling (×2) is standard; a smaller factor uses less memory but reallocates more often. The choice is a time/space trade-off.

Type-generic arrays

To hold arbitrary types, store void * pointers or use macros/_Generic. A void * array is generic but loses type safety and stores pointers, not values.

Common Mistakes

• Forgetting to check realloc (leaks/UB).
• Using p = realloc(p, ...) directly (leaks on failure).
• Confusing size and capacity.
• Forgetting to free the internal buffer.

Undefined Behavior

• Accessing beyond size (but within capacity) reads uninitialized memory —

UB for non-unsigned char types. VERIFIED

• Use-after-free of the internal buffer.

Portability

• Plain C, fully portable. Growth and allocation behavior are standard.

Under the Hood

The realloc-based growth is the same mechanism malloc uses internally. A contiguous buffer is cache-friendly (c.perf.2).

Practical Usage

• Use dynamic arrays for collections whose size is unknown.
• Use a stack for parsing, backtracking, and function-call-like state.

Exercises

1. Implement vec_push, vec_get, and vec_free. 2. Add vec_pop and vec_insert (with shifting). 3. Implement a stack on top of the vector and test push/pop order.

Deep Challenge

Implement a type-generic dynamic array using void * and a size_t element size, with push and get copying bytes via memcpy. Discuss the type-safety and aliasing implications.

Related Concepts

• c.memory.2 — allocation.
• c.mem.ownership — ownership.
• c.ds.4 — queues/ring buffers.

References

• ISO C §7.22.3 (allocation); standard data-structure literature.

Verification

• Amortized O(1) push is standard CS. VERIFIED
• realloc failure handling. VERIFIED
• No example was executed during generation unless noted. `Execution not

verified.`

Progress

• [ ] Read
• [ ] Understand
• [ ] Complete examples
• [ ] Complete exercises
• [ ] Complete deep challenge

Concept checkboxes

• [ ] Dynamic array (size/capacity)
• [ ] Amortized O(1) push
• [ ] Stack push/pop

Mastery levels