我最近遇到了下面的链接,我发现它非常有趣.

http://en.wikipedia.org/wiki/XOR_linked_list

>通用调试工具
不能跟随XOR链,制作
调试比较困难; [1]
>内存减少的代价
用法是代码的增加
复杂性,使维护更多
昂贵;
>大多数垃圾收集计划都有
不能使用数据结构
不包含文字指针;
>指针的XOR未定义
一些上下文(例如C语言),
虽然许多语言提供了一些
两种类型之间的转换
指针和整数;
>如果指针将是不可读的
一个不是遍历列表 – 为
例如,如果指向列表的指针
item包含在另一个数据中
结构体;
>在遍历列表时,您需要
记得的地址
以前访问过的节点
计算下一个节点的地址.

现在我想知道这是否仅适用于低级语言,或者在C#中是否也可以？

是否有任何类似的选项可以用C#产生相同的结果？

解决方法:

TL; DR我很快用C#写了一个概念验证XorLinkedList implementation.

使用C#中的unsafe代码绝对可以实现.但是有一些限制：

> XorLinkedList必须是“非托管结构”,即它们不能包含托管引用
>由于C#泛型的限制,链表不能是通用的(甚至没有T：struct的地方)

后者似乎是因为您不能将泛型参数限制为非托管结构.在T：struct的位置,您还允许包含托管引用的结构.

这意味着您的XorLinkedList只能保存原始值,如整数,指针或其他非托管结构.

C#中的低级编程

private static Node* _ptrXor(Node* a, Node* b)
{
    return (Node*)((ulong)a ^ (ulong)b);//very fragile
}

我知道,非常脆弱. C#指针和IntPtr不支持XOR运算符(可能是个好主意).

private static Node* _allocate(Node* link, int value = 0)
{
    var node = (Node*) Marshal.AllocHGlobal(sizeof (Node));
    node->xorLink = link;
    node->value = value;
    return node;
}

之后不要忘记Marshal.FreeHGlobal这些节点(实现完整的IDisposable模式并确保将免费调用放在if(disposing)块之外.

private static Node* _insertMiddle(Node* first, Node* second, int value)
{
    var node = _allocate(_ptrXor(first, second), value);
    var prev = _prev(first, second);
    first->xorLink = _ptrXor(prev, node);
    var next = _next(first, second);
    second->xorLink = _ptrXor(node, next);
    return node;
}

结论

就个人而言,我绝不会在C#中使用XorLinkedList(当我编写内存分配器或内核数据结构等低级系统内容时,可能会使用C语言.在任何其他设置中,存储效率的小幅提升实在不值得痛苦.事实上,你不能将它与C#中的托管对象一起使用,这对于日常编程来说几乎没用.

此外,今天的存储几乎是免费的,即使是主内存也是如此,如果你使用的是C#,你很可能并不关心存储.我已经读过某个地方,CLR对象标题大约是40个字节,所以这个指针将是你最不关心的问题;)