Freestyle linked lists tricks

Freestyle linked lists tricks

December 31, 2025

nullprogram.com/blog/2025/12/31/

Linked lists are a data structure basic building block, with especially<br>flexible allocation behavior. They’re not just a useful starting point,<br>but sometimes a sound foundation for future growth. I’m going to start<br>with the beginner stuff, then without disrupting the original linked<br>list, enhance it with new capabilities.

Linked list basics

For the sake of an interesting example, I’m will demonstrate with the same<br>concept as last time I talked about data structures: a collection<br>of key/value strings, in the form of an environment variables. This time<br>in linked list form:

typedef struct {<br>char *data;<br>ptrdiff_t len;<br>} Str;

uint64_t hash64(Str);<br>bool equals(Str, Str);

typedef struct Env Env;<br>struct Env {<br>Env *next;<br>Str key;<br>Str value;<br>};

It will be sourced from some string, formatted like the env program:

Str input = S(<br>"EDITOR=vim\n"<br>"HOME=/home/user\n"<br>"PATH=/bin:/usr/bin\n"<br>"SHELL=/bin/bash\n"<br>"TERM=xterm-256color\n"<br>"USER=user\n"<br>"SHELL=/bin/sh\n" //<br>);

And all the parser heavy lifting will be done by our ever-handy cut<br>function:

typedef struct {<br>Str tail;<br>Str head;<br>} Cut;

Cut cut(Str, char);

The simplest way to build up a linked list is like a stack, pushing<br>objects into the front. Zero-initialized head pointer, point the new<br>node at it, then make that node the new head element:

Env *parse_reversed(Str s, Arena *a)<br>Env *head = 0; // 1<br>for (Cut line = {s}; line.tail.len;) {<br>line = cut(line.tail, '\n');<br>Cut pair = cut(line.head, '=');<br>Env *env = new(a, 1, Env);<br>env->key = pair.head;<br>env->value = pair.tail;<br>env->next = head; // 2<br>head = env; // 3<br>return head;

That’s it, a complete linked list implementation in three lines of code.<br>No big deal. Because of the bump allocator, nodes are packed in order in<br>memory, so the usual cache objections for linked lists do not apply. LIFO<br>semantics mean the linked list is in reverse order from the source order.<br>If we’re doing a linear scan through the linked list, the last entry in<br>the source wins, which may be what you wanted:

Str lookup_linear(Env *env, Str key)<br>for (Env *var = env; var; var = var->next) {<br>if (equals(key, var->key)) {<br>return var->value;<br>return (Str){};

// ...<br>Env *env = parse_reversed(input, &scratch);<br>Str value = lookup_linear(env, S("SHELL")); //

It’s just one more line of code to maintain the original order, using a<br>very simple double-pointer technique:

Env *parse_ordered(Str s, Arena *a)<br>Env *head = 0; // 1<br>Env **tail = &head; // 2<br>for (Cut line = {s}; line.tail.len;) {<br>// ...<br>*tail = env; // 3<br>tail = &env->next; // 4<br>return head;

No branches necessary, nor dummy nodes. A pointer to the last pointer in<br>the list works even for empty lists. The tail pointer is unneeded once<br>the list is complete. This form has queue behavior.

Faster look-up with a tree

If you’re doing many look-ups, or if the list is long, those linear scans<br>to find items in the list are not ideal. We can introduce an intrusive<br>hash map, in the form of a hash trie, by adding two more pointers<br>to the linked list:

typedef struct Env Env;<br>struct Env {<br>Env *next;<br>Env *child[2]; //<br>Str key;<br>Str value;<br>};

I’ve found it’s simplest to construct a node into the hash map, then link<br>it onto the list tail. That constructor looks like this:

Env *new_env(Arena *a, Env **env, Str key, Str value)<br>for (uint64_t h = hash64(key); *env; h 1) {<br>env = &(*env)->child[h>>63];<br>*env = new(a, 1, Env);<br>(*env)->key = key;<br>(*env)->value = value;<br>return *env;

Then we swap that into the head/tail version in place of the original<br>new macro call:

Env *parse_mapped(Str s, Arena *a)<br>Env *head = 0;<br>Env **tail = &head;<br>for (Cut line = {s}; line.tail.len;) {<br>// ...<br>Env *env = new_env(a, &head, pair.head, pair.tail);<br>*tail = env;<br>tail = &env->next;<br>return head;

This is now a linked list and a hash map at the same time, built-up piece<br>by piece without any resizing. We still have the original linked list, but<br>we can now search it in log time. The look-up function resembles the<br>constructor:

Str lookup_logn(Env *env, Str key)<br>for (uint64_t h = hash64(key); env; h 1) {<br>if (equals(key, env->key)) {<br>return env->value;<br>env = env->child[h>>63];<br>return (Str){};

Because of the FIFO semantics, it finds the first match in the source:

Env *env = parse_mapped(input, &scratch);<br>Str value = lookup_logn(env, S("SHELL")); //

The other matches are also in the tree, and we can find those as well by<br>continuing traversal. That is, it’s already a multi-map. This particular<br>interface can’t pick up where it left off, but we can build one that does<br>using an iterator/cursor:

typedef struct {<br>uint64_t hash;<br>Str key;<br>Env *env;<br>} EnvIter;

EnvIter new_enviter(Env *env, Str key)<br>return (EnvIter){hash64(key), key, env};

Str enviter_next(EnvIter *it)<br>while (it->env) {<br>Env *cur = it->env;<br>it->env = it->env->child[it->hash>>63];<br>it->hash 1;<br>if (equals(it->key, cur->key)) {<br>return cur->value;<br>return (Str){};

Update...