异或链表

链表节点本身只存储一个指针，可以用于节省内存（但是 Python、Java 需要建立节点 id 映射，就达不到目的了）

代码示例

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int Value;
    uintptr_t Xor;
} Node;

Node* CreateNode(int value) {
    Node* node = malloc(sizeof(*node));
    memset(node, 0, sizeof(*node));
    node->Value = value;
    return node;
}

typedef struct {
    Node* begin;
    Node* end;
} LinkedList;

void Append(LinkedList* l, int value) {
    if (l->end == NULL) {
        assert(l->begin == NULL);
        l->end = CreateNode(value);
        l->begin = l->end;
    } else {
        Node* node = CreateNode(value);
        node->Xor = (uintptr_t) l->end;
        l->end->Xor ^= (uintptr_t) node;
        l->end = node;
    }
}

Node* NextNode(Node* node, uintptr_t* pre) {
    Node* next = (Node*) (node->Xor ^ *pre);
    *pre = (uintptr_t) node;
    return next;
}

int main() {
    LinkedList l = {0};
    for (int x = 5; x <= 10; x++) {
        Append(&l, x);
    }

    uintptr_t pre = 0;
    for (Node* iter = l.begin; iter; iter = NextNode(iter, &pre)) {
        printf("%d\n", iter->Value);
    }

    return 0;
}

#include <iostream>

struct Node {
    int Value;
    uintptr_t Xor;

    explicit Node(int v) noexcept : Value(v), Xor(0) {}
};

struct LinkedList {
    Node* begin = nullptr;
    Node* end = nullptr;

    LinkedList() = default;

    // disable copy to avoid double free / shallow-copy issues
    LinkedList(const LinkedList&) = delete;
    LinkedList& operator=(const LinkedList&) = delete;

    LinkedList(LinkedList&& other) noexcept : begin(other.begin), end(other.end) { other.begin = other.end = nullptr; }
    LinkedList& operator=(LinkedList&& other) noexcept {
        if (this != &other) {
            this->~LinkedList(); // free existing
            begin = other.begin;
            end = other.end;
            other.begin = other.end = nullptr;
        }
        return *this;
    }

    ~LinkedList() {
        uintptr_t prev = 0;
        Node* curr = begin;
        while (curr) {
            uintptr_t curr_addr = reinterpret_cast<uintptr_t>(curr);
            uintptr_t next_addr = curr->Xor ^ prev;
            Node* next = reinterpret_cast<Node*>(next_addr);
            delete curr;
            prev = curr_addr;
            curr = next;
        }
        begin = end = nullptr;
    }

    void Append(int value) {
        if (end == nullptr) { // empty list
            Node* n = new Node(value);
            begin = end = n;
        } else {
            Node* n = new Node(value);
            n->Xor = reinterpret_cast<uintptr_t>(end);
            end->Xor ^= reinterpret_cast<uintptr_t>(n);
            end = n;
        }
    }

    template <typename Fn>
    void ForEach(Node* begin, Fn fn) const {
        uintptr_t prev = 0;
        Node* curr = begin;
        while (curr) {
            fn(curr->Value);
            uintptr_t curr_addr = reinterpret_cast<uintptr_t>(curr);
            uintptr_t next_addr = curr->Xor ^ prev;
            Node* next = reinterpret_cast<Node*>(next_addr);
            prev = curr_addr;
            curr = next;
        }
    }
};

int main() {
    LinkedList l;
    for (int x = 5; x <= 10; ++x) {
        l.Append(x);
    }

    l.ForEach(l.end, [](int v) { std::cout << v << "\n"; });

    return 0;
}

package main

import (
	"fmt"
	"unsafe"
)

type Node struct {
	Value int
	Xor   uintptr
}

type LinkedList struct {
	begin *Node
	end   *Node
}

func CreateNode(value int) *Node {
	return &Node{Value: value}
}

func (l *LinkedList) Append(value int) {
	if l.end == nil {
		node := CreateNode(value)
		l.begin = node
		l.end = node
	} else {
		node := CreateNode(value)
		node.Xor = uintptr(unsafe.Pointer(l.end))
		l.end.Xor ^= uintptr(unsafe.Pointer(node))
		l.end = node
	}
}

func NextNode(node *Node, pre *uintptr) *Node {
	nextPtr := node.Xor ^ *pre
	*pre = uintptr(unsafe.Pointer(node))
	if nextPtr == 0 {
		return nil
	}
	return (*Node)(unsafe.Pointer(nextPtr))
}

func main() {
	var l LinkedList
	for x := 5; x <= 10; x++ {
		l.Append(x)
	}

	var pre uintptr = 0
	for iter := l.end; iter != nil; iter = NextNode(iter, &pre) {
		fmt.Println(iter.Value)
	}
}

# Java 类似
from typing import Any, Generator, Literal


class Node:
    __slots__ = ("value", "xor")

    def __init__(self, value):
        self.value = value
        self.xor = 0  # xor of ids


class XorLinkedList:
    def __init__(self):
        self.begin = None
        self.end = None
        # keep a map id -> node to be able to dereference and to keep nodes alive
        self._nodes = {}

    def _store(self, node):
        self._nodes[id(node)] = node

    def append(self, value):
        if self.end is None:
            node = Node(value)
            self._store(node)
            self.begin = node
            self.end = node
        else:
            node = Node(value)
            self._store(node)
            node.xor = id(self.end)
            self.end.xor ^= id(node)
            self.end = node

    def _next_node(self, node, prev_id) -> tuple[None, Literal[0]] | tuple[Any, int]:
        next_id = node.xor ^ prev_id
        if next_id == 0:
            return None, 0
        nxt = self._nodes.get(next_id)
        if nxt is None:
            raise RuntimeError("corrupt xor list or node reclaimed")
        return nxt, id(node)

    def iter_values(self, begin: Node | None) -> Generator[Any, Any, None]:
        prev_id = 0
        node = begin
        while node is not None:
            yield node.value
            node, prev_id = self._next_node(node, prev_id)


if __name__ == "__main__":
    l = XorLinkedList()
    for x in range(5, 11):
        l.append(x)
    for v in l.iter_values(l.end):
        print(v)

Reference

Programming Party Tricks