Polyglot
› Languages › C › data structures
C § data-structures

Data structures

The C language provides three native composition primitives — array, struct, union — and one family of references — pointers — out of which every other data structure is built. The standard library does not include containers: there is no list type, no hash table, no balanced tree, no growable string. Programs that need such structures either implement them directly or link against a third-party library. The brevity of the type-construction surface, paired with the absence of generics, accounts for the most distinctive aspect of writing data structures in C: each type and each structure is hand-fitted, with no shared parameterisation across element types.

Arrays

An array is a contiguous sequence of objects of the same type. The size is part of the type and must be known when the array is declared:

int   a[10];                 /* an array of ten ints */
char  s[]    = "hello";      /* size deduced: 6 (with the terminator) */
double m[3][4];              /* a two-dimensional array, row-major */

The standard guarantees contiguous storage: &a[i] + 1 == &a[i+1] is well-defined for any valid i. The implication is that an array can be passed by giving its first address and its length, and indexed efficiently.

In most expression contexts, an array decays to a pointer to its first element. The principal contexts in which this does not occur are sizeof (yields the byte size of the whole array) and & (yields a pointer to the array). The decay is the reason that array dimensions are not propagated through function calls — see Pointers for the full treatment.

Multidimensional arrays

A multidimensional array is an array of arrays. Storage is row-major: the rightmost index varies fastest:

int matrix[3][4];   /* 3 rows of 4 ints; matrix[1][2] is the third element of the second row */

For dynamically-sized matrices, two conventions appear:

  • A flat array indexed manually: int *matrix = malloc(rows * cols * sizeof *matrix); matrix[i*cols + j].
  • An array of pointers: int **matrix = malloc(rows * sizeof *matrix); for (i) matrix[i] = malloc(cols * sizeof **matrix).

The flat form has better cache behaviour and a single allocation; the pointer-array form admits ragged structure (rows of different lengths) at the cost of an extra indirection.

C99’s variable-length arrays permit an automatic array whose size is computed at runtime, but they impose a stack cost and are not universally supported (MSVC does not implement them); their use in production code is typically discouraged.

Variable-length arrays

void process(size_t n) {
    int buf[n];                       /* C99 VLA — automatic storage */
    /* ... use buf ... */
}

The VLA exists for the duration of the function. The implementation is on the stack; large n produces stack overflow. C11 made VLA support optional (the implementation defines __STDC_NO_VLA__ if absent). For dynamic sizes, malloc is the safer choice.

Structures

A structure aggregates named members with their own types:

typedef struct {
    char    name[32];
    int     age;
    double  salary;
} employee;

employee alice = { "Alice", 30, 50000.0 };
employee bob   = { .name = "Bob", .age = 28, .salary = 47000.0 };  /* designated */

Structures are first-class values: they may be assigned, passed by value, returned by value, and stored in arrays or as members of other structures. The exception is the absence of a built-in equality operation: s1 == s2 is not defined for structures. Equality must be tested member by member or with memcmp (the latter being safe only for structures without padding).

Member layout

Members are stored in declaration order, with implementation-defined padding inserted to satisfy alignment requirements:

struct example {
    char  c1;     /* offset 0,  size 1 */
                  /* offset 1,  3 bytes of padding */
    int   x;     /* offset 4,  size 4 */
    char  c2;     /* offset 8,  size 1 */
                  /* offset 9,  3 bytes of trailing padding */
};
/* sizeof(struct example) == 12 on a typical platform */

The trailing padding ensures that, if the structure is placed in an array, the next instance is correctly aligned. Reordering members from largest to smallest typically reduces total padding.

The offsetof macro from <stddef.h> returns the byte offset of a member; the operator is type-safe and portable:

size_t off = offsetof(struct example, x);   /* 4 on the layout above */

Anonymous structures and unions

C11 permits a structure or union member without a name:

struct vector {
    union {
        struct { double x, y, z; };       /* anonymous struct */
        double components[3];
    };
};

struct vector v = { .x = 1, .y = 2, .z = 3 };
double first = v.components[0];           /* same storage as v.x */

The anonymous-member rule simplifies access: the inner members appear as if they were members of the enclosing structure. The construction is the conventional way to overlay alternative views of the same storage.

Bit-fields

A structure member may be declared as a bit-field, occupying a specified number of bits:

struct flags {
    unsigned visible    : 1;
    unsigned movable    : 1;
    unsigned focused    : 1;
    unsigned priority   : 5;       /* values 0–31 */
};

Bit-fields pack multiple small integer fields into the same word. Their layout — bit order within the underlying storage, alignment of the underlying storage — is implementation-defined; portable programs do not rely on a specific layout.

The principal uses are protocol headers (where the layout is dictated externally and the implementation is expected to honour it) and compact flag arrays. For the latter, manual bit manipulation with &, |, << is often clearer.

Unions

A union holds at most one of its members at a time; all members occupy the same storage. The size of the union is at least the size of its largest member, plus padding for alignment:

typedef union {
    uint32_t  word;
    uint8_t   bytes[4];
} word32;

word32 w;
w.word = 0xCAFEF00D;
printf("%02x %02x %02x %02x\n",
       w.bytes[0], w.bytes[1], w.bytes[2], w.bytes[3]);

Reading a member other than the one most recently written is type punning. The standard’s view of type punning has shifted between revisions; the cleanly-defined alternative is memcpy between objects of compatible storage size, which the compiler is required to honour without breaking strict aliasing.

The principal use of unions in modern C is the tagged union — a structure containing a discriminator and a union of payloads. Treated in Pattern matching.

Enumerations

An enumeration declares a set of named integer constants:

enum day { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY };
enum day today = WEDNESDAY;

Enumerators are integer constants; without an =, each is one greater than its predecessor and the first is 0. Explicit values are permitted:

enum bits { READ = 1, WRITE = 2, EXEC = 4 };

Until C23, enumerators were always of type int, regardless of the declared values. C23 permits a fixed underlying type:

enum status : uint8_t { OK = 0, ERROR = 1, TIMEOUT = 2 };

The standard does not impose a constraint that values assigned to a variable of enumerated type belong to the declared set; the type system treats enum day as compatible with int. Enumerations are principally a notational device, not a type-safety mechanism.

Linked structures

Linked structures are composed by storing pointers within structures; the structure points to others of the same type, forming chains, trees, or graphs.

Singly-linked list

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

node *list_prepend(node *head, int v) {
    node *n = malloc(sizeof *n);
    if (!n) return head;
    n->value = v;
    n->next  = head;
    return n;
}

void list_free(node *head) {
    while (head) {
        node *next = head->next;
        free(head);
        head = next;
    }
}

The structure is self-referential: a node contains a pointer to another node. Within the structure body, the type is incomplete — its size is not yet known — but pointer types to incomplete types are well-defined.

Doubly-linked list

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

Doubly-linked lists permit O(1) removal given a node pointer; the trade-off is the second pointer’s storage and the additional bookkeeping.

Trees

typedef struct tree_node {
    int               key;
    struct tree_node *left, *right;
} tree_node;

Binary search trees, red-black trees, and AVL trees are conventional implementations. None is in the standard library; production C code uses libraries (the BSD <sys/queue.h> macros, the Linux kernel’s list.h, third-party glib) or hand-rolled implementations.

Hash tables

The standard library does not include a hash table. The conventional implementations are open addressing with linear probing or separate chaining with a linked-list bucket. Each implementation is hand-fit to the value type; C’s lack of generics means that a hash table for int keys and a hash table for string keys are written as separate structures, often with the same algorithm but distinct types.

A minimal open-addressing skeleton:

typedef struct { uint64_t key; int value; bool occupied; } slot;

typedef struct {
    slot   *slots;
    size_t  capacity;
    size_t  count;
} hashmap;

static size_t hash(uint64_t key) {
    /* a mixing function */
    key ^= key >> 33; key *= 0xff51afd7ed558ccd;
    key ^= key >> 33; key *= 0xc4ceb9fe1a85ec53;
    key ^= key >> 33;
    return (size_t)key;
}

static slot *probe(hashmap *m, uint64_t key) {
    size_t i = hash(key) & (m->capacity - 1);
    while (m->slots[i].occupied && m->slots[i].key != key)
        i = (i + 1) & (m->capacity - 1);
    return &m->slots[i];
}

The construction requires the capacity to be a power of two (so that & (capacity - 1) is the cheap form of modulus), a load-factor threshold for resizing, and a deletion strategy (tombstones or rehashing). It is a non-trivial body of code per type, which is why C programs frequently link against generic libraries that solve the problem once.

Generic-pointer containers

A common pattern for general-purpose containers in C is to operate on void * and require the user to manage element sizes:

typedef struct {
    void   *data;
    size_t  count;
    size_t  capacity;
    size_t  element_size;
} vector;

bool vector_push(vector *v, const void *element) {
    if (v->count == v->capacity) {
        size_t new_cap = v->capacity ? v->capacity * 2 : 8;
        void  *new_data = realloc(v->data, new_cap * v->element_size);
        if (!new_data) return false;
        v->data     = new_data;
        v->capacity = new_cap;
    }
    memcpy((char *)v->data + v->count * v->element_size, element, v->element_size);
    ++v->count;
    return true;
}

The pattern matches the qsort/bsearch model of taking element sizes explicitly. The trade-offs are loss of type-checking (the compiler cannot ensure the caller passes the right element type), loss of inlining (each access goes through memcpy), and ergonomics that lag what a typed container offers. Production C codebases commonly use generic-pointer containers for non-performance-critical structures and hand-fit, type-specialised structures where speed matters.

The standard generic algorithms

The standard library provides two generic algorithms in <stdlib.h>:

  • qsort(base, count, size, cmp) — sorts count elements of size size starting at base, using cmp to compare two elements.
  • bsearch(key, base, count, size, cmp) — performs a binary search; returns a pointer to the matching element or NULL.

The comparator takes const void * arguments and returns a negative, zero, or positive integer:

int cmp_int(const void *a, const void *b) {
    int ai = *(const int *)a, bi = *(const int *)b;
    return (ai > bi) - (ai < bi);
}

int arr[] = {3, 1, 4, 1, 5, 9, 2, 6};
qsort(arr, 8, sizeof *arr, cmp_int);

int target = 4;
int *found = bsearch(&target, arr, 8, sizeof *arr, cmp_int);

Both functions take a void * pointer to the data and a size_t element size. The comparator is the type-specific part; the algorithm is fixed. The construction is C’s substitute for the type-parameterised algorithms of newer languages.