xor · 指针压缩

XOR 链表：两个指针压成一个

双向链表每个节点存 prev 和 next 两个地址，才换来「向前 / 向后都能走」。XOR linked list 发现：既然两个方向都靠地址，不如只存它们的异或—— $both = prev \oplus next$ ，一个字段顶两个，指针空间立省一半。代价是不能凭空持有任意单个节点：必须知道某个邻居的地址，才能从 both 里解出另一边。下面用遍历 / 插入 / 删除三种操作单步演示这套地址异或：遍历时手里始终攥着 (prev, cur) 一对地址，每步靠 $next = cur.both \oplus prev$ 推出下一个，正反向同一套公式；增删则只在端点动手，把变更落到相邻两个节点的 both 上。也正是这一点，暴露了它「只能在端点或已知邻居处增删」的结构性弱点。

原理根基是异或的自反性： $a \oplus b \oplus a = b$ 。 既然 $both = prev \oplus next$ ，那么用手里已知的 prev 再异或一次就能消掉它，剩下 next: $both \oplus prev = (prev \oplus next) \oplus prev = next$ 。反过来从尾往头走，用已知的 next 异或也能解出 prev——同一个 both 字段，从哪头来就解出哪头去，这正是「一个指针走双向」的来源。

**端点把 null 当地址 0 处理。**头节点没有前驱，prev 视作地址 0，于是 $both = 0 \oplus nextAddr = nextAddr$ ——头节点的 both 恰好就是后继地址；同理尾节点 $both = prevAddr \oplus 0 = prevAddr$ 。遍历时只要起步令 prev = 0，公式 $next = both \oplus prev$ 在端点自动给出正确结果，无需特判。算笔账：双向每节点两个指针，64 位机上 16 字节；XOR 只留一个，8 字节，指针开销正好减半。

增删只能在端点或已知邻居处做，这是它的结构性弱点。上面的 insert / delete 演示都落在头 / 尾：端点的另一侧是 null（地址 0），手里天然攥着「邻居 = null」这半边，于是能从 both 解出另一边、再把变更异或回相邻节点。可一旦想在中间任意位置动手——比如只凭一个引用拿到了某个中间节点 x——就卡住了：单独一个 $x.both = prev \oplus next$ 是两个地址异或成的一团，缺少任一邻居地址就无法把 prev 和 next 拆开，既找不到前驱也找不到后继，改写无从下手。换句话说，持有节点 ≠ 能操作节点，必须额外带上它的某个邻居地址。对比双向链表：拿到 x 就有 x.prev / x.next，中间增删当场 $O(1)$ 。这正是 XOR 链表对随机访问 / 通用容器不友好、现代工程几乎不用它的根因。

还有两处实现层面的硬伤。其一，字段里存的是异或后的裸地址，不是真正的引用：在有 GC 或内存安全检查的语言里，回收器顺着字段找不到被引用对象（地址被异或「藏」起来了），既不安全也无法实现；调试时打印 both 也只是一串看不懂的数。其二，指针算术本身就被现代语言（Java / Go / Rust safe 子集）禁止。所以它更像一道经典的指针位运算 trick / 面试题，而非实用结构。