data-structures 异或链接列表

示例

一个异或链表也被称为内存效率链表。这是双向链接列表的另一种形式。这高度依赖于XOR逻辑门及其属性。

为什么将其称为“内存有效链表”？

之所以这样称呼，是因为与传统的双向链表相比，它使用的内存更少。

这与双向链接列表不同吗？

是的，是的。

甲双链表正存储两个指针，它指向下一个及前一个节点。基本上，如果要返回，则转到back指针指向的地址。如果要前进，请转到next指针指向的地址。就像是：

甲内存效率链表，或即链表XOR是仅具有一个指针，而不是两个。这将前一个地址（addr(prev)）与下一个地址（addr(next)）XOR（^）进行存储。当您想移至下一个节点时，您需要进行某些计算，然后找到下一个节点的地址。转到上一个节点是相同的。它就像是：

它是如何工作的？

要了解链表的工作原理，您需要了解XOR（^）的属性：

|-------------|------------|------------|
|    Name     |   Formula  |    Result  |
|-------------|------------|------------|
| Commutative |    A ^ B   |    B ^ A   |
|-------------|------------|------------|
| Associative | A ^ (B ^ C)| (A ^ B) ^ C|
|-------------|------------|------------|
| None (1)    |    A ^ 0   |     A      |
|-------------|------------|------------|
| None (2)    |    A ^ A   |     0      |
|-------------|------------|------------|
| None (3)    | (A ^ B) ^ A|     B      |
|-------------|------------|------------|

现在，我们将其放在一边，看看每个节点存储了什么。

第一个节点或头存储，0 ^ addr (next)因为没有先前的节点或地址。看起来像这样。

然后第二个节点存储addr (prev) ^ addr (next)。看起来像这样。

列表的尾部没有任何下一个节点，因此存储addr (prev) ^ 0。看起来像这样。

从头移动到下一个节点

假设您现在位于第一个节点或节点A上。现在您要移至节点B。这是这样做的公式：

Address of Next Node = Address of Previous Node ^ pointer in the current Node

因此，这将是：

addr (next) = addr (prev) ^ (0 ^ addr (next))

由于这是头，因此先前的地址将只是0，因此：

addr (next) = 0 ^ (0 ^ addr (next))

我们可以删除括号：

addr (next) = 0 ^ 0 addr (next)

使用该none (2)属性，我们可以说0 ^ 0它将始终为0：

addr (next) = 0 ^ addr (next)

使用该none (1)属性，我们可以将其简化为：

addr (next) = addr (next)

您获得了下一个节点的地址！

从一个节点移动到下一个节点

现在，我们处于一个中间节点，该节点具有上一个和下一个节点。

让我们应用公式：

Address of Next Node = Address of Previous Node ^ pointer in the current Node

现在替换值：

addr (next) = addr (prev) ^ (addr (prev) ^ addr (next))

删除括号：

addr (next) = addr (prev) ^ addr (prev) ^ addr (next)

使用该none (2)属性，我们可以简化：

addr (next) = 0 ^ addr (next)

使用该none (1)属性，我们可以简化：

addr (next) = addr (next)

你明白了！

从一个节点移动到您先前所在的节点

如果您不理解标题，则基本上意味着如果您在节点X上，并且现在已移至节点Y，则您想返回先前访问的节点，或者基本上是节点X。

这不是一项繁琐的任务。请记住，我之前已经提到过，您将原来的地址存储在一个临时变量中。因此，您要访问的节点的地址位于一个变量中：

addr (prev) = temp_addr

从一个节点移动到上一个节点

这与上面提到的不同。我的意思是说，您在节点Z上，现在您在节点Y上，并且想要转到节点X。

这几乎与从一个节点移至下一个节点相同。反之亦然。编写程序时，将使用与从一个节点移至下一个节点时提到的步骤相同的步骤，只是在列表中查找的元素要比查找下一个元素的早。

C中的示例代码

/* C/C++ Implementation of Memory efficient Doubly Linked List */
#include <stdio.h>
#include <stdlib.h>
 
// 高效内存双链表的节点结构
struct node
{
    int data;
    struct node* npx;  /* XOR of next and previous node */
};
 
/* returns XORed value of the node addresses */
struct node* XOR (struct node *a, struct node *b)
{
    return (struct node*) ((unsigned int) (a) ^ (unsigned int) (b));
}
 
/* 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)
{
    // 为新节点分配内存
    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 list is not empty, then npx of current head node will be XOR 
       of new node and node next to current head */
    if (*head_ref != NULL)
    {
        // *(head_ref)->npx is XOR of NULL and next. So if we do XOR of 
        // NULL，我们得到下一个
        struct node* next = XOR((*head_ref)->npx,  NULL);
        (*head_ref)->npx = XOR(new_node, next);
    }
 
    // 换头
    *head_ref = new_node;
}
 
// 向前打印双向链表的内容
void printList (struct node *head)
{
    struct node *curr = head;
    struct node *prev = NULL;
    struct node *next;
 
    printf ("Following are the nodes of Linked List: \n");
 
    while (curr != NULL)
    {
        // 打印当前节点
        printf ("%d ", curr->data);
 
        // get address of next node: curr->npx is next^prev, so curr->npx^prev
        // 将是下一个^上一个^上一个是下一个
        next = XOR (prev, curr->npx);
 
        // 更新下一个和下一个迭代的curr
        prev = curr;
        curr = next;
    }
}
 
// 驱动程序测试上述功能
int main ()
{
    /* Create following Doubly Linked List
       head-->40<-->30<-->20<-->10   */
    struct node *head = NULL;
    insert(&head, 10);
    insert(&head, 20);
    insert(&head, 30);
    insert(&head, 40);
 
    // 打印创建的列表
    printList (head);
 
    return (0);
}

上面的代码执行两个基本功能：插入和横向。

• 插入：这是通过函数执行的insert。这将在开始处插入一个新节点。调用此函数时，它将新节点作为头，并将先前的头节点作为第二节点。

• 遍历：这是通过功能执行的printList。它只是遍历每个节点并输出值。

请注意，C / C ++标准未定义指针的XOR。因此，上述实现可能无法在所有平台上都有效。

参考文献

• https://cybercruddotnet.wordpress.com/2012/07/04/complicating-things-with-xor-linked-lists/

• http://www.ritambhara.in/memory-efficient-doubly-linked-list/comment-page-1/

• http://www.geeksforgeeks.org/xor-linked-list-a-memory-ficient-doubly-linked-list-set-2/

请注意，我从main自己的答案中获得了很多内容。