# Freestyle linked lists tricks

DevFeed: [Freestyle linked lists tricks](<https://devfeed.tech/articles/freestyle-linked-lists-tricks-20508.md>)

Original publisher: [Read original article](<https://nullprogram.com/blog/2025/12/31/>)

Published: 2025-12-31T11:59:59Z

Content type: tutorial

Language: en

Sources: [Chris Wellons](<https://devfeed.tech/sources/chris-wellons.md>)

Topics: [Data structures](<https://devfeed.tech/topics/data-structures.md>), [data](<https://devfeed.tech/topics/data.md>), [Parser](<https://devfeed.tech/topics/parser.md>)

Tags: [c](<https://devfeed.tech/tags/c.md>), [code](<https://devfeed.tech/tags/code.md>), [data](<https://devfeed.tech/tags/data.md>), [structure](<https://devfeed.tech/tags/structure.md>)

## AI overview

A tutorial on implementing linked lists for key/value environment-style data, beginning with a simple stack-based list and then preserving the list while adding queue behavior and an intrusive hash trie for faster lookups. It discusses allocation, memory layout, ordering semantics, and duplicate-key behavior.

## Source excerpt

Linked lists are a data structure basic building block, with especially flexible allocation behavior. They're not just a useful starting point, but sometimes a sound foundation for future growth. I'm going to start with the beginner stuff, then without disrupting the original linked list, enhance it with new capabilities. Linked list basics For the sake of an interesting example, I'm will demonstrate with the same concept as last time I talked about data structures: a collection of key/value strings, in the form of an environment variables. This time in linked list form: typedef struct { char *data; ptrdiff_t len; } Str; uint64_t hash64(Str); bool equals(Str, Str); typedef struct Env Env; struct Env { Env *next; Str key; Str value; }; It will be sourced from some string, formatted like the env program: Str input = S( "EDITOR=vim\n" "HOME=/home/user\n" "PATH=/bin:/usr/bin\n" "SHELL=/bin/bash\n" "TERM=xterm-256color\n" "USER=user\n" "SHELL=/bin/sh\n" // <- repeated entry ); And all the parser heavy lifting will be done by our ever-handy cut function: typedef struct { Str tail; Str head; } Cut; Cut cut(Str, char); The simplest way to build up a linked list is like a stack, pushing objects into the front. Zero-initialized head pointer, point the new node at it, then make that node the new head element: Env *parse_reversed(Str s, Arena *a) { Env *head = 0; // 1 for (Cut line = {s}; line.tail.len;) { line = cut(line.tail, '\n'); Cut pair = cut(line.head, '='); Env *env = new(a, 1, Env); env->key = pair.head; env->value = pair.tail; env->next = head; // 2 head = env; // 3 } return head; } That's it, a complete linked list implementation in three lines of code. No big deal. Because of the bump allocator, nodes are packed in order in memory, so the usual cache objections for linked lists do not apply. LIFO semantics mean the linked list is in reverse order from the source order. If we're doing a linear scan through the linked list, the last entry in the source wins, which ma