Data Structures

The standard library hands you an ArrayList and a hash map. These chapters build them. A linked list first, because it is the smallest structure that forces you to answer who allocates and who frees. Then the same list made generic by a comptime type function, which is all Zig's generics are. Then the intrusive lists std actually ships today, which look nothing like the ones in older tutorials. Then a binary search tree, the sorted input that ruins it, and the rotations that fix it. Finally a hash map, where deleting without a tombstone quietly loses your keys.

1. Who allocates and who frees is decided once per container, and then it shows up in every signature that container has.
2. A generic container is a comptime function that takes a type and returns a type. ArrayList(u8) is a call.
3. The lists std ships today are intrusive: the node lives inside your struct. Tutorials written a year ago show a different API.
4. A hash map that deletes without leaving a tombstone loses every key that probed past the hole.

6 chapters.

• A Linked List by HandThe smallest structure that needs an allocator, an optional pointer and a deinit that gets the order right.
• Making It GenericZig has no generics syntax. A generic container is a function that takes a type and returns a type, evaluated at compile time.
• The Lists in std Are Intrusivestd.SinglyLinkedList is not generic and does not hold your data. You embed its node in your struct and walk back out with @fieldParentPtr.
• A Binary Search TreeTwo pointers instead of one buys ordered iteration and O(log n) lookup, on a condition the structure does nothing to enforce.
• Keeping It BalancedStore a height, check it after every insert, repair it with a local rotation. Four cases, none longer than five lines.
• A Hash Map from ScratchOpen addressing with linear probing, growth at 75%, and the tombstone that looks like a hack until you delete without one.