标签: xor-linkedlist

在阅读有关C数据结构的书时,我遇到了"内存高效的双重链接列表"这个术语.它只有一行说一个内存有效的双向链表使用比普通双链表更少的内存,但做同样的工作.没有更多的解释,也没有给出任何例子.只是有人认为这是从一本期刊中获取的,而在"Brackets"中则是"Sinha".

在Google上搜索后,我最接近的就是这个.但是,我什么都听不懂.

有人能解释一下C中的内存高效双链表是什么？它与正常的双向链接列表有什么不同？

编辑:好的,我犯了一个严重的错误.看到我上面发布的链接,是文章的第二页.我没有看到有第一页,并认为给出的链接是第一页.文章的第一页实际上给出了解释,但我不认为它是完美的.它只讨论了Memory-Efficient Linked List或XOR Linked List的基本概念.

XOR链表基本上是链表的有效版本,其存储前一节点和下一节点的地址以仅使用单个指针来实现双链表.我想知道是否有可能在Java中实现,因为它没有指针.在C中,这可以通过

 /* Insert a node at the begining of the XORed linked list and makes the
    newly inserted node as head */
void insert(struct node **head_ref, int data)
{
    // Allocate memory for new node
    struct node *new_node  = (struct node *) malloc (sizeof (struct node));
    new_node->data = data;

    /* Since new node is being inserted at the begining, npx of new node
       will always be XOR of current head and NULL */
    new_node->npx = XOR(*head_ref, NULL);

    /* If linked …

我想为xor链表编写java代码.有人可以建议我如何在引用之间执行xor操作吗？

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

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

• 通用调试工具不能遵循XOR链,使调试更加困难; [1]
• 内存使用量减少的代价是代码复杂性的增加,使维护成本更高;
• 大多数垃圾收集方案不适用于不包含文字指针的数据结构;
• 指针的异或未在某些上下文中定义(例如,C语言),尽管许多语言在指针和整数之间提供某种类型的转换;
• 如果没有遍历列表,则指针将是不可读的 - 例如,如果指向列表项的指针包含在另一个数据结构中;
• 在遍历列表时,您需要记住先前访问的节点的地址,以便计算下一个节点的地址.

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

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

我正在尝试在Common Lisp上实现XOR链接列表,但我需要获取一个变量的地址来对其执行任何按位操作.有没有办法获取变量的内存地址,类似于python的id()函数？

考虑到 C++17 中引入的语义变化（例如在具有正确地址和类型的指针自 C++17 以来是否仍然始终是有效指针中进行了讨论） ，XOR 链接列表以一种对我来说看起来很可疑的方式使用指针算术。）。它们现在会导致未定义的行为吗？如果是这样，可以通过洗涤来拯救它们吗？

编辑：

维基百科文章仅包含有关指针和整数之间转换的简短注释。我默认（现在明确声明）指针首先被转换为足够大小的整数类型以适合它们，然后对整数进行异或。因此，操作理论中列出的 XOR 属性保证只有从指针获得一次的整数才会被转换回它们。根据标准，从指针到整数的实际映射可以是任意注入。除此之外我不依赖任何假设。

标准是否允许使用它们并访问仍然存在的对象？C++17 之前？从 C++17 开始？

我正在阅读 XOR链表(来自维基百科).但我在理解它时遇到了一些问题.

我没有得到以下段落.

要从某个点开始遍历任一方向的列表,您需要两个连续项的地址,而不仅仅是一个.如果两个连续项目的地址相反,您将最终以相反的方向遍历列表.

我对此几乎没有疑问:

1. 它是如何(XOR链表本身)实际工作的？

   (如果你通过给出一些例子证明你的答案是合理的.通过取一些地址然后做相应的计算.)

2. 我该如何实现它？关于实施的简要概念.

3. 实际上它在哪里或可以使用？看起来真的有用吗？

我正在阅读 XOR 链表，我想到了一个问题，在我Is it possible to have a circular XOR linked list?看来，即使我们以某种方式构建了这样一个列表，也不可能在给定列表头节点的情况下遍历它。例如 - 让链表包含 3 个节点：A、B 和 C。

|
v
A ---> B ---> C

A->xor = B ^ C
B->xor = A ^ C
C->xor = A ^ B

由于我们已经给出head了列表，即A在这种情况下，我们将无法向前或向后移动，因为我们必须至少知道B或C中的一个才能移动。由于我们无法遍历它，因此我们也无法构建它。

我的想法正确吗？或者我错过了什么？

在Data Structures and Algorithms Made Easy中,struct内存高效的内存列表如下,

struct LinkNode
{
 int data;
 struct LinkNode* ptrdiff;
}

在ptrdiff,将完成上一个和下一个节点的xoring.例如,前一个节点的地址为100,下一个节点的地址为500.

所以,在ptrdiff地址将是400.现在,如何通过了解其地址的xoring,如何移动到下一个或上一个节点(就像我们在双向链接列表中那样)？

我错过了这里的任何一步吗？

这是我的xor链表实现的代码

#include<iostream>

using namespace std;

struct node
{
    int v;
    node *next;
};

node *start=NULL;
node *end=NULL;

node *newnode(int v)
{
    node *np=new node;
    np->v=v;
    np->next=NULL;
    return np;
}

//returns the xor of two nodes
node *xor(node *a,node *b)
{
    return (node*)((long long)(a)^(long long)(b));
}

void insert(node *current,node *prev,node *np)
{
    if(start==NULL)
    {
        np->next=xor(prev,NULL);
        start=np;
        end=np;
    }
    else
    {
        insert(xor(prev,current->next),current,np);
    }
}

void displayforward(node *start,node *prev)
{
    if(start==NULL) return ;
    cout<<start->v<<"-> ";
    displayforward(xor(start->next,prev),start);
}

void displayBackward(node *end, node *prev){
    if(end …