Data Structures

The standard library gives you an ArrayList and a hash map, and these chapters build them. The growable array is first, because each later container uses one, and the array is only a length, a capacity and a doubling rule. Next is a linked list, the smallest structure that makes you decide who allocates and who frees. A comptime type function then makes the list generic, and that function is all that Zig generics are. Then come the intrusive lists that std ships today, which are very different from the lists in older tutorials. The last chapters show a binary search tree, the sorted input that unbalances it and the rotations that fix it. Then a hash map shows how a delete without a tombstone loses keys and reports no error.

1. When the buffer doubles on each growth, append is amortised O(1). If the buffer grows by a fixed number of slots, n appends cost O(n^2).
2. Each container decides once who allocates and who frees. That decision then appears in every signature of the container.
3. A generic container is a comptime function that takes a type and returns a type. ArrayList(u8) is a call.
4. The lists that std ships today are intrusive: the node is inside your struct. Tutorials from a year ago show a different API.
5. If a hash map deletes a key and leaves no tombstone, the map loses every key that probed past the hole.

7 chapters.

• A Growable ArrayA length, a capacity, and one rule for what occurs when the length reaches the capacity.
• A Linked List by HandThe smallest structure that needs an allocator, an optional pointer and a deinit with the correct order.
• Make It GenericZig has no generics syntax. A generic container is a function that takes a type and returns a type at compile time.
• The Lists in std Are Intrusivestd.SinglyLinkedList is not generic and does not hold your data. Put its node in your struct and get back to the struct with @fieldParentPtr.
• A Binary Search TreeTwo pointers instead of one give ordered iteration and O(log n) lookup, on a condition that the structure does not enforce.
• Keep It BalancedStore a height, check it after each insert, and repair the shape with a local rotation. Four cases, and each case has five lines or fewer.
• A Hash Map from ScratchOpen addressing with linear probing, growth at 75%, and the tombstone. The tombstone looks like a hack, but it makes delete work.