There was a recent conversation[0] about the switch in Zig master branch to use of 'intrusive' linked lists, in preference to the textbook kind. These will usually have better performance, but the stdlib implementation comes with some disadvantages as well: the Node types are fully generic, so it's possible to link two structs together which aren't supposed to be in the same list. It uses @fieldParentPtr to retrieve the struct pointer, so if this sort of confusion happens, the result will probably be illegal memory access. Basically it pushes key operations out of the type system and onto the runtime, where they can cause trouble. I've had in mind for a while a different approach, one which is type safe, so I wrote zelda. This is more of a comptime 'mixin', taking a struct type and adding node capabilities to it, constructing a SinglyLinkedList or DoublyLinkedList type for handling the lists themselves. It's a relatively straightforward translation of the stdlib types, passing a superset of the tests and adding a few additional operations and some diagnostic functions. I had a lot of fun with it, and I think it answers some of the (fair) criticisms surfaced in the last conversation. It's also a nice illustration of what comptime is capable of, in my opinion. If you like this kind of thing, check it out! |