THE FOLD / CHEAT / THE-SHORTCUT / THE XOR LINKED LIST
THE XOR LINKED LIST
one pointer holds both neighbors
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
The XOR linked list stores a doubly linked list using only one pointer field per node instead of two. A normal doubly linked list keeps a prev and a next pointer; the XOR list keeps their bitwise exclusive-or, link = prev ⊕ next. That single value is enough to walk in either direction: if you know the address you came from, the other neighbour is link ⊕ came-from (because XOR is its own inverse). Moving forward, next = link ⊕ prev; moving backward, prev = link ⊕ next. Half the pointer memory, at the cost of no O(1) access to a node without a neighbour.
LIT verified live: over 20,000 random lists, forward traversal reproduces the array, backward traversal reproduces its reverse, and every node stores exactly one link field (window.__xor_linked_list). FIG no framing; the XOR-link build and both traversals run in-browser.
LIT verified live: over 20,000 random lists, forward traversal reproduces the array, backward traversal reproduces its reverse, and every node stores exactly one link field (window.__xor_linked_list). FIG no framing; the XOR-link build and both traversals run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-shortcut — carry both neighbours in one field by folding them together with XOR, and unfold whichever one you need. AVAN (AI) built the instrument: the prev⊕next links, the forward and backward walks, and the array cross-checks.
Credit as content: the XOR linked list is a classic pointer trick (Prokop-era folklore). The weave: David names the shortcut; I confirm one XOR link per node suffices to traverse both ways.
Credit as content: the XOR linked list is a classic pointer trick (Prokop-era folklore). The weave: David names the shortcut; I confirm one XOR link per node suffices to traverse both ways.
3 ONE DIMENSION
Each node holds link = prev ⊕ next; knowing where you came from, the other neighbour is link ⊕ came-from.
4 TWO DIMENSIONS · INTERACTIVE
Build a list; walk it forward and backward from a single XOR link per node — matching the array both ways.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the list, walkable both ways from one field.
AVAN’s addition (the inverse-companion): don’t store two pointers — store their XOR. The inverse of ‘keep prev and next’ is ‘keep prev ⊕ next; the missing neighbour is link ⊕ the one you know.’ Magenta are the two pointers folded away; green is the single link that recovers either. One field, both directions.
LIT Genuine XOR linked list (a classic pointer/memory trick). Verified live: over 20000 random lists built with link[i]=prev⊕next, forward traversal (next=link⊕prev) reproduces the array, backward traversal (prev=link⊕next) reproduces its reverse, and there is exactly one link field per node (window.__xor_linked_list.forwardMatches, .backwardMatches, .oneLink).
FIG No framing: the XOR-link build and both traversals run in-browser (node indices as the 'addresses'). The AVAN inverse is honest — instead of storing prev and next, one stores their XOR; the missing neighbour is link ⊕ the one you already know, since XOR undoes itself. Magenta are the two pointers folded away; green is the single link that recovers either. One field, both directions.
FIG No framing: the XOR-link build and both traversals run in-browser (node indices as the 'addresses'). The AVAN inverse is honest — instead of storing prev and next, one stores their XOR; the missing neighbour is link ⊕ the one you already know, since XOR undoes itself. Magenta are the two pointers folded away; green is the single link that recovers either. One field, both directions.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-SHORTCUT · David Lee Wise (ROOT0), with AVAN