Data Structures

Zig's standard library provides efficient, allocator-aware data structures that compose cleanly with the rest of the language. Unlike languages that hide allocation behind garbage collection or smart pointers, Zig makes every allocation explicit — you pass an allocator in, you call deinit when you are done. There are no hidden costs and no surprises at runtime. The two structures you will reach for most often are ArrayList for ordered collections that grow dynamically and HashMap for key-value lookups. Beyond the standard library, Zig's comptime system makes it straightforward to write your own generic data structures that work safely across any type.

ArrayList: Dynamic Collections

std.ArrayList(T) is Zig's dynamic array. It owns a heap-allocated slice that grows automatically as you append elements. You start it empty with .empty and pass an allocator to each operation that may allocate — append, deinit, and so on — so the list itself stores no allocator and every allocation stays explicit at the call site. The underlying elements are always accessible through the .items field, which is a plain slice you can iterate, index, or pass to any function that accepts a slice.

const std = @import("std");

pub fn main() !void {
    var gpa: std.heap.DebugAllocator(.{}) = .init;
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var scores: std.ArrayList(i32) = .empty;
    defer scores.deinit(allocator);

    try scores.append(allocator, 88);
    try scores.append(allocator, 95);
    try scores.append(allocator, 72);
    try scores.append(allocator, 91);

    std.debug.print("Scores ({} total):\n", .{scores.items.len});
    for (scores.items, 0..) |score, i| {
        std.debug.print("  [{}] {}\n", .{ i, score });
    }

    // orderedRemove preserves order at O(n) cost
    _ = scores.orderedRemove(1);

    std.debug.print("After removing index 1:\n", .{});
    for (scores.items) |score| {
        std.debug.print("  {}\n", .{score});
    }
}

append may trigger a reallocation, so it takes the allocator, returns an error union, and requires try. The defer scores.deinit(allocator) pattern ensures the heap memory is released even if a later operation fails. When order does not matter, swapRemove replaces the target element with the last one and removes the tail in O(1) — use it instead of orderedRemove for large lists where preserving insertion order is not important.

HashMap: Key-Value Lookups

std.StringHashMap(V) maps string keys to values of type V. For integer or struct keys, std.AutoHashMap(K, V) selects an appropriate hash function automatically based on the key type. Both follow the same allocator-in, deinit-to-free pattern.

const std = @import("std");

pub fn main() !void {
    var gpa: std.heap.DebugAllocator(.{}) = .init;
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var inventory = std.StringHashMap(u32).init(allocator);
    defer inventory.deinit();

    try inventory.put("sword", 3);
    try inventory.put("shield", 1);
    try inventory.put("potion", 10);

    // get returns ?V — null if the key is absent
    if (inventory.get("potion")) |count| {
        std.debug.print("Potions in stock: {}\n", .{count});
    }

    // getOrPut inserts a default and avoids a second lookup
    const result = try inventory.getOrPut("arrow");
    if (!result.found_existing) {
        result.value_ptr.* = 0;
    }
    result.value_ptr.* += 24;

    std.debug.print("Arrows: {}\n", .{inventory.get("arrow").?});

    // Iterate over all entries
    std.debug.print("Full inventory:\n", .{});
    var it = inventory.iterator();
    while (it.next()) |entry| {
        std.debug.print("  {s}: {}\n", .{ entry.key_ptr.*, entry.value_ptr.* });
    }
}

get returns an optional — null when the key is absent, otherwise the value. getOrPut is the idiomatic way to insert a default or update an existing entry without two separate map lookups. It returns a struct with found_existing and a writable value_ptr. An important ownership note: StringHashMap does not copy or own the key strings it stores. If you allocate a key dynamically, you are responsible for freeing it when you remove the entry.

Building Generic Data Structures

Zig does not have a generics keyword. Instead, you write a function that accepts a type at compile time and returns a new struct type built around it. This pattern gives you full generic behavior through ordinary comptime evaluation.

const std = @import("std");

fn Stack(comptime T: type) type {
    return struct {
        const Self = @This();
        items: std.ArrayList(T),
        allocator: std.mem.Allocator,

        pub fn init(allocator: std.mem.Allocator) Self {
            return .{ .items = .empty, .allocator = allocator };
        }

        pub fn deinit(self: *Self) void {
            self.items.deinit(self.allocator);
        }

        pub fn push(self: *Self, value: T) !void {
            try self.items.append(self.allocator, value);
        }

        pub fn pop(self: *Self) ?T {
            if (self.items.items.len == 0) return null;
            return self.items.pop();
        }

        pub fn peek(self: *const Self) ?T {
            const len = self.items.items.len;
            if (len == 0) return null;
            return self.items.items[len - 1];
        }

        pub fn isEmpty(self: *const Self) bool {
            return self.items.items.len == 0;
        }
    };
}

pub fn main() !void {
    var gpa: std.heap.DebugAllocator(.{}) = .init;
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    var stack = Stack([]const u8).init(allocator);
    defer stack.deinit();

    try stack.push("first");
    try stack.push("second");
    try stack.push("third");

    std.debug.print("Top: {?s}\n", .{stack.peek()});

    while (!stack.isEmpty()) {
        const val = stack.pop().?;
        std.debug.print("Popped: {s}\n", .{val});
    }
}

@This() inside the returned struct refers to the struct type itself, enabling self-referential method definitions. The same Stack function works equally for i32, f64, or any struct type without changes to the implementation — the compiler generates a separate concrete type for each instantiation.

Try It Yourself

Build a word frequency counter. Split a sentence into words and use StringHashMap to count how many times each word appears. Use getOrPut to avoid redundant lookups.

const std = @import("std");

pub fn main() !void {
    var gpa: std.heap.DebugAllocator(.{}) = .init;
    defer _ = gpa.deinit();
    const allocator = gpa.allocator();

    const sentence = "the quick brown fox jumps over the lazy dog the fox";

    var freq = std.StringHashMap(u32).init(allocator);
    defer freq.deinit();

    var words = std.mem.splitScalar(u8, sentence, ' ');
    while (words.next()) |word| {
        const entry = try freq.getOrPut(word);
        if (!entry.found_existing) {
            entry.value_ptr.* = 0;
        }
        entry.value_ptr.* += 1;
    }

    std.debug.print("Word frequencies:\n", .{});
    var it = freq.iterator();
    while (it.next()) |entry| {
        std.debug.print("  {s}: {}\n", .{ entry.key_ptr.*, entry.value_ptr.* });
    }
}

Try extending this example: filter out words that appear only once, or find the word with the highest count by tracking a running maximum during the iteration loop.

Key Takeaways

std.ArrayList(T) is Zig's dynamic array — start it with .empty, pass the allocator to append and deinit, access elements through .items, and always pair creation with defer deinit(allocator)
orderedRemove preserves element order at O(n) cost; swapRemove is O(1) when order does not matter
std.StringHashMap(V) and std.AutoHashMap(K, V) provide O(1) average lookups; get returns an optional, getOrPut avoids double lookups on insert-or-update patterns
HashMap does not own string keys — free any dynamically allocated keys yourself before or after removing entries
Generic data structures use fn(comptime T: type) type with @This() for self-referential method types — no separate generics syntax required
Use std.StringHashMap(void) as a set type when you only need membership testing, not stored values

Pro Tip: When you need ordered key-value iteration — something HashMap does not guarantee — reach for std.ArrayHashMap. It maintains insertion order, supports O(1) appends and lookups, and lets you index entries by position, making it ideal for configuration tables, ordered caches, or any structure where you care about both fast lookup and deterministic traversal order.

Next Steps