A linked list is a standard data structure where elements of the list know who comes before and after them and the list itself knows who is at the start and the end. It's easy enough to roll your own linked list, so let's do it. Strictly speaking, one does not need to do this; Zig's standard library has things like std.TailQueue which work great. But it's not too hard (she says having spent an afternoon hashing out precisely how to do it), and it feels good to know what goes into things like this. So let's define a node in a linked list.

const Node = struct {
    next: ?*Node,
    prev: ?*Node,
    data: *Data,
};

Okay hi, hello, welcome to Zig. Let's talk through it. So we're declaring a new struct type called Node. Because we don't plan on altering the type itself, we mark it const (as opposed to var). This struct has three fields, next, prev and data. The data field is a pointer to a struct with type Data. We haven't yet defined Data, but that's okay. Okay and pointers? It's funny, I grew up reading my dad's C programming language books, but many powerful programming languages don't have a concept of a pointer; pointers are messy. The idea is that the pointer is not the object itself, but a little thing that says "hi, you can find what you're looking for at this memory address." Zig has pointers.

The usefulness of pointers becomes clear when we consider the next and prev fields: forgetting about the ? for a moment, notice that they're of type Node themselves! So we have to use a pointer here, otherwise a Node would have to contain a Node which contains a Node etc. etc. Okay anyway the ? says that our Node entries are allowed to be null, that is, not to point to something valid. (Notice that this implies that the data entry must always be valid! That's amazing!)

Cool, so far so good. Let's put nodes into a queue… literally:

const Queue = struct {
  const Node = struct {
      next: ?*Node,
      prev: ?*Node,
      data: *Data,
  };
  head: ?*Node,
  tail: ?*Node,
  size: usize,
};

If you know a little C, we did something a bit surprising: we put the definition of a Node inside the definition of Queue. Zig lets you do this; it effectively "namespaces" Node, which is maybe neither here nor there, so that's all I'll say about it.

Okay so a queue has a head and a tail, which may be null, and a size, which is a usize (an unsigned integer type appropriate for, well, sizes). How should we interact with it? let's write some functions. Zig lets us put them inside of Queue too, but I'll present them by themselves. Okay warning, for, like, exposition purposes, I'm giving you incorrect code here.

fn push(self: *Queue, data: Data) void {
  var new_node = Node{
      .next = null,
      .prev = null,
      .data = data,
  };
  if (self.tail) |n| {
      self.tail = &new_node;
      n.next = &new_node;
      new_node.prev = n;
  } else {
      std.debug.assert(self.size == 0);
      self.tail = &new_node;
      self.head = &new_node;
  }
  self.size += 1;
}
  

In fact, while this looks beguilingly like correct code, it won't compile, and not just because we haven't defined the Data type! I'll get to that in a moment. First let's make sense of more Zig syntax.

We declare a function with the fn keyword. This function is named push and it takes in two arguments: self, which is a pointer to a Queue, and data, which is some Data. The function returns void, i.e. it gives you nothing back. We declare variables with the var keyword. We're making new_node a struct object of type Node and assigning to its fields by accessing them with the dot syntax. (Shortly we'll meet another way to declare elements of struct type.) The if statement has an interesting |n| bit after it. The point is that self.tail is allowed to be null. We say if it's not null, then give us what it is, and capture that in a new (const) variable n. Since self.tail expects to be a pointer to a node and not a node, we assign to it the address or reference of new_node by using the & operator, like in C. So you should read the if statement as saying "if self.tail is not null, we assign the reference of new_node to it, we set the next field of the old tail, i.e. n, to new_node (or its address) and set the prev field of the new node to n." If not, the else statement says "well first of all, the size had better be zero or we're bailing, and if so we set the head and tail of self to our new node." Finally in either case we add one to the size of our queue.

In C, it's very easy to leak memory; just call malloc (short for memory allocation, but I like to imagine a little devil, "mal" meaning bad, named malloc) without later calling free. In Zig, it's still possible to leak memory, but the language will try to help you out. First of all, we need to choose an allocator, which is of type std.mem.Allocator. Zig gives you several choices; maybe the best one for most purposes is the "general purpose allocator". Let's grab it.

var allocator: std.mem.Allocator = undefined;

pub fn main() void {
  var general_allocator = std.heap.GeneralPurposeAllocator(.{}) {};
  allocator = general_allocator.allocator();
  defer _ = general_allocator.deinit();
}

It's possible that this is an anti-pattern: I've declared my allocator as if it were a static variable in C. It's not initialized until we enter main, where we grab it in two stages. In seamstress, I then tend to pass the allocator to other source files in their init functions.

Anyway, so much for the allocator. We'll often call allocator.alloc() to make many copies of something (the Zig word is "slices"), or allocator.create() to create single objects.