XOR 链接列表

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

为什么这称为内存高效链接列表？

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

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

是的，确实如此。

一个双链表正存储两个指针，其在下一和前一节点指向。基本上，如果你想回去，你会转到 back 指针指向的地址。如果你想继续前进，你会转到 next 指针指向的地址。就像是：

http://i.stack.imgur.com/t1RDM.gif

一个内存效率链表，或即异或链表是仅具有一个指针，而不是两个。这将先前的地址（addr(prev)） XOR （^）存储到下一个地址（addr(next)）。如果要移动到下一个节点，可以执行某些计算，并查找下一个节点的地址。这与前一个节点相同。它像是：

它是如何工作的？

要了解链表的工作原理，你需要知道 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。看起来像这样 。

从 Head 移动到下一个节点

假设你现在位于第一个节点或节点 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>
 
// Node structure of a memory efficient doubly linked list
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)
{
    // 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 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 
        // it with NULL, we get next
        struct node* next = XOR((*head_ref)->npx,  NULL);
        (*head_ref)->npx = XOR(new_node, next);
    }
 
    // Change head
    *head_ref = new_node;
}
 
// prints contents of doubly linked list in forward direction
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)
    {
        // print current node
        printf ("%d ", curr->data);
 
        // get address of next node: curr->npx is next^prev, so curr->npx^prev
        // will be next^prev^prev which is next
        next = XOR (prev, curr->npx);
 
        // update prev and curr for next iteration
        prev = curr;
        curr = next;
    }
}
 
// Driver program to test above functions
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);
 
    // print the created list
    printList (head);
 
    return (0);
}

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

• 插入： 由 insert 函数执行。这会在开头插入一个新节点。调用此函数时，它将新节点作为头，将前一个头节点作为第二个节点。

• 遍历： 这是由 printList 函数执行的。它只是遍历每个节点并打印出值。

请注意，指针的 XOR 不是由 C / C++标准定义的。因此，上述实现可能无法在所有平台上运行。

参考

• 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-efficient-doubly-linked-list-set-2/

请注意，我从主要的答案中获取了很多内容。