c# - XOR链表

我最近遇到了一个链接，下面的链接很有趣。

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

通用调试工具
无法遵循异或链，使得
调试更加困难； [1]

内存减少的价格
用法是代码的增加
复杂性，使维护工作更多
昂贵的;

大多数垃圾回收方案都可以
不适用于具有此功能的数据结构
不包含文字指针；

指针的

XOR未在中定义
一些上下文(例如C语言)，
尽管许多语言提供了一些
之间的类型转换
指针和整数；

如果以下情况，指针将不可读
一个没有遍历列表-因为
例如，如果指向列表的指针
项目包含在另一个数据中
结构体;

在遍历列表时，您需要
记住地址
先前访问的节点以
计算下一个节点的地址。

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

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

最佳答案

TL; DR 我很快用C#编写了概念证明XorLinkedList implementation。

使用C#中的unsafe代码绝对可以做到这一点。但是，有一些限制:

XorLinkedList必须是“非托管结构”，即，它们不能包含托管引用

由于C#泛型的限制，链接列表不能是泛型的(即使使用where T : struct也不可以)

后者似乎是因为您不能将通用参数限制为非托管结构。仅使用where T : struct，您还可以允许包含托管引用的结构。

这意味着您的XorLinkedList只能保存基本值，例如int，指针或其他非托管结构。

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语言中使用XorLinkedList。在任何其他设置中，存储效率的小幅增长确实不值得。事实上，您无法将其与C#中的托管对象一起使用，这使其在日常编程中几乎毫无用处。

另外，今天的存储几乎是免费的，即使是主内存也是如此，如果您使用的是C#，您可能不太在乎存储。我读过某个地方的CLR对象 header 大约有40个字节，因此这个指针将是您最不用担心的问题；)